Coursera Flash Sale
40% Off Coursera Plus for 3 Months!
Grab it
Explore computational complexity theory through this comprehensive lecture series from Carnegie Mellon University's Spring 2017 undergraduate course taught by Ryan O'Donnell. Master fundamental concepts including Turing machines, time and space complexity classes, NP-completeness, and advanced topics like the polynomial hierarchy and interactive proofs. Begin with basic computational models and progress through key theorems including the Time Hierarchy Theorem, Cook-Levin Theorem, Savitch's Theorem, and the Immerman-Szelepcsényi Theorem. Examine complexity classes such as P, NP, coNP, PSPACE, and BPP while learning essential techniques like reductions, padding arguments, and oracle constructions. Investigate randomized complexity, interactive proof systems, and modern perspectives on hardness within P. Conclude with an analysis of why the P vs. NP problem remains one of computer science's greatest challenges. The course corresponds to Part III of Sipser's textbook and requires prior knowledge of basic computer science theory including big-O notation and Turing machines.
