Nov 21, 2024  
2014-2015 Catalog 
    
Catalog Navigation
  Publication Home
  About Harvey Mudd College
  Introduction
  Student Life
  Admission & Financial Aid
  Academic Program
  HMC Common Core
  Department of Biology
  Department of Chemistry
  Department of Computer Science
  Department of Engineering
  Department of Humanities, Social Sciences, and the Arts
  Department of Mathematics
  Department of Physics
  Interdisciplinary Programs
  Other Programs
  Study Abroad
  Programs of Study
  Course Descriptions
  Academic Regulations
  General Regulations
  Faculty
  Senior Administration
  Academic Calendar 2014-2015
  Archived Catalogs
HELP
2014-2015 Catalog [ARCHIVED PUBLICATION] Use the dropdown above to select the current catalog.

CSCI142 HM - Complexity Theory

Credit(s): 3

Libeskind-Hadas, Pippenger (Mathematics). 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. (Fall, alternate years) (Crosslisted as MATH167 HM )

Prerequisite(s): CSCI081 HM