Skip to Main Content

COMP.5100 Computational Complexity Theory (Formerly 91.510)

Id: 008139 Credits Min: 3 Credits Max: 3


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-Reqs. COMP 5020 Foundations of CS, and COMP 5030 Algorithms.

View Current Offerings