Dec 03, 2020  
2019-2020 Catalog 
2019-2020 Catalog [ARCHIVED PUBLICATION] Use the dropdown above to select the current catalog.

MATH167 HM - Complexity Theory

Credit(s): 3

Instructor(s): Pippenger, Libeskind-Hadas (Computer Science), Staff (Pomona)

Offered: Fall

Description: Brief review of computability theory, followed by a rigorous treatment of complexity theory. The complexity classes P, NP, and the Cook-Levin Theorem. Approximability of NP-complete problems. The polynomial hierarchy, PSPACE-completeness, L and NL-completeness, #P-completeness. IP and Zero-knowledge proofs. Randomized and parallel complexity classes. The speedup, hierarchy, and gap theorems. (Crosslisted as CSCI142 HM )

Prerequisite(s): (CSCI060 HM  or CSCI042 HM ) and MATH055 HM