CATALOG DESCRIPTION: An introduction to computational complexity beyond the P versus NP question. Topics include the polynomial-time hierarchy and alternation, counting complexity, interactive proofs and circuit complexity.
REQUIRED TEXTBOOKS: There is no textbook for the course.
COURSE COORDINATOR : Instructor -- Lance Fortnow
COURSE GOALS: To give an overview of computational complexity.
PREREQUISITES : EECS 335 (Introduction to Theory of Computing) or permission of instructor.
- Complexity Zoo, list and defintions of hundreds of complexity classes.
- Lectures in Computational Complexity, textbook draft by Jin-Yi Cai
- Complexity Theory: A Modern Approach textbook draft by Sanjeev Arora and Boaz Barak
- Foundations of Complexity, a series of weblog posts I wrote.
- P v NP
- SAT is NP-complete
- Ladner's Theorem
- Mahaney's Theorem
- Alternation and PSPACE
- Polynomial-Time Hierarchy
- P/poly, Karp-Lipton
- Circuit Complexity
- Razborov Montone Clique
- Time-Space Tradeoffs for SAT
- Randomness: RP, co-RP, BPP, ZPP
- AIT in co-RP
- BPP in PH
- MA, AM, GNI in AM
- Public coin for GNI with lower bound lemma
- Counting Complexity
- Toda's theorem
- IP = PSPACE
- PCP theorem
COMPUTER USAGE: None
HOMEWORK ASSIGNMENTS: Weekly
LABORATORY PROJECTS: None
GRADES: Grades are based on homework and participation
ABET CONTENT CATEGORY: