CS 5814

Introduction to Computational Complexity

Course Description

Course information provided by the 2026-2027 Catalog.

Explores the power and limitations of efficient computation. Understanding how the notion of efficient computation changes with respect to resources such as time, space, randomness, advice, and interaction. Concrete computational models that we will study will include Turing machines, Boolean circuits, Decision trees, and Branching Programs. Advanced topics may include error-correcting codes, probabilistic checkable proofs, and circuit lower bounds.

Prerequisites CS 4820.

Last 4 Terms Offered 2024FA

Learning Outcomes

• Define and classify fundamental complexity classes (e.g., P, NP, coNP, PSPACE) and explain relationships among them.
• Construct and analyze reductions to establish computational hardness of problems.
• Prove NP-completeness of natural problems by designing reductions from canonical complete problems.
• Analyze the computational complexity of algorithms and problems using formal models.
• Compare and evaluate different computational models (deterministic, randomized, nondeterministic, space-bounded) and their relative power.
• Explain and apply hardness assumptions in the design of basic cryptographic primitives (e.g., one-way functions, pseudorandom generators), and analyze their security at a high level.
• Describe and analyze interactive proof systems (e.g., IP, PCP), including their soundness and completeness guarantees and implications for complexity classes.
• Formulate and communicate rigorous proofs of complexity-theoretic statements using precise mathematical language.

View Enrollment Information