Computational Complexity Theory: P vs NP and Oracle Machines

Theoretical computer science relies on understanding what computers can solve efficiently and what remains beyond practical reach. This course guides you step by step through core complexity concepts, beginning with deterministic and nondeterministic models before exploring deeper structural questions. You will develop a solid grasp of formal computation models, the fundamental P versus NP problem, and why traditional proof techniques face structural limits. What you'll learn: Understand core computational models including Turing machines and formal time bounds; Analyze fundamental complexity classes including P, NP, and complement classes; Explore the deterministic and nondeterministic time hierarchy theorems and their proofs; Examine oracle Turing machines and the mechanics of relativized computation; Understand the Baker-Gill-Solovay theorem establishing oracle separations where P equals NP and P does not equal NP; Evaluate modern perspectives on relativization barriers and proof techniques in theoretical computer science. The text starts with fundamental terminology, definitions, and proof conventions before moving systematically toward time hierarchies and oracle-based computations. This course is designed for beginners in theoretical computer science, computer science students, and programmers interested in computational limits, with no advanced background in complexity theory required. Start reading today to build a rigorous foundation in computational complexity.