Id: 008139
Credits Min: 3
Credits Max: 3
Description
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.
Prerequisites
Pre-Reqs. COMP 5020 Foundations of CS, and COMP 5030 Algorithms.
View Current Offerings