91.510 Computational Complexity Theory

Computational Complexity Theory

Course Details
Min Credits 3
Max Credits 3
Course ID 8139
Status Active

This course covers polynomial-time hierarchy and polynomial space, circuit complexity, structure of NP, probabilistic machines and complexity classes, complexity of counting, interactive proof systems, probabilistically checkable proofs, complexity of approximation problems, and average-case NP-completeness.

Pre/Co-Requisites: Pre-Reqs. 91.502 Foundations of CS, and 91.503 Algorithms.