|
Oct 07, 2024
|
|
|
|
2021-2022 Catalog [ARCHIVED PUBLICATION] Use the dropdown above to select the current catalog.
|
CSCI142 HM - Complexity Theory Credit(s): 3
Instructor(s): Pippenger (Mathematics)
Description: Brief review of computability theory through Rice’s Theorem and the Recursion Theorem 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 MATH167 HM )
Prerequisite(s): CSCI081 HM
|
|