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.

 

On-Line Resources

Tentative Topics:

  • 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-Smolensky
  • 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 
  • Permanent
  • Toda's theorem
  • IP = PSPACE
  • PCP theorem

COMPUTER USAGE: None

HOMEWORK ASSIGNMENTS: Weekly
LABORATORY PROJECTS: None
GRADES: Grades are based on homework and participation
COURSE OBJECTIVES:
ABET CONTENT CATEGORY: