COMP.5100 Computational Complexity Theory (Formerly 91.510)
Id: 008139
Credits: 3-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
Course prerequisites/corequisites are determined by the faculty and approved by the curriculum committees. Students are required to fulfill these requirements prior to enrollment. For courses offered through online or GPS delivery, students are responsible for confirming with the instructor or department that all enrollment requirements have been satisfied before registering.