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