Undergraduate Complexity Theory

This inaugural lecture introduces the CMU 15-455 curriculum and begins the formal definition of computation, laying the groundwork for complexity theory.

This lecture provides a foundational introduction to Turing Machines, exploring their structure and operational principles as a model for computation, referencing Sipser, Chapter 3.1, 3.3.

The session examines various Turing Machine variants and their simulation capabilities, demonstrating the robustness of the core model and its equivalence to other computational constructs.

This lecture introduces time complexity as a measure of computational efficiency and explores the concept of Universal Turing Machines, fundamental to understanding computability limits.

This lecture formally establishes the Time Hierarchy Theorem, proving that for any given time-constructible function, there are problems that can be solved in strictly more time.

This lecture delves into the class P, discussing problems solvable in polynomial time and examining specific examples like PATH and RELPRIME to illustrate its scope.

This lecture focuses on the Satisfiability Problem (SAT), a fundamental problem in computational complexity, exploring its structure and significance.

This lecture introduces the complexity class NP, defining problems for which a given solution can be verified in polynomial time, crucial for understanding computational hardness.

This lecture explores the concept of nondeterminism within computation, particularly in the context of Turing Machines and its implications for complexity classes.

The lecture explains polynomial-time reductions, a key technique for demonstrating the relative hardness of computational problems within complexity theory.

Guest lecturer Yu Zhao explores NP-Completeness and delivers a detailed exposition of the seminal Cook-Levin Theorem, establishing SAT as the first NP-complete problem.

Guest lecturer David Witmer demonstrates various NP-completeness reductions, showcasing how to prove the hardness of new problems by relating them to known NP-complete problems.

This lecture covers the relationship between search and decision problems, padding arguments, and introduces dichotomy theorems in computational complexity.

This lecture presents Ladner's Theorem, demonstrating the existence of problems in NP that are neither in P nor NP-complete, and discusses Mahaney's Theorem.

This lecture introduces the complexity class coNP, defined by problems whose complements are in NP, and explores its relationship to P and NP.

This lecture introduces space complexity, analyzing the amount of memory a computational model requires, and defines key space complexity classes like L and PSPACE.

This lecture explores Savitch's Theorem, establishing a fundamental relationship between deterministic and non-deterministic space complexity, and introduces the class NL.

The lecture defines NL-completeness and details logspace reductions, demonstrating how problems within NL can be related to a core set of hard problems.

This lecture traces the path from P-completeness to PSPACE-completeness, culminating in the analysis of TQBF as a canonical PSPACE-complete problem.

This lecture provides a comprehensive treatment of the Immerman-Szelepcsényi Theorem, proving that nondeterministic space classes are closed under complementation.