(Formerly CS159)

Introduction to Computational Complexity

Course Home Page:
Location:CIT Lubrano
Exam Group:13
Semester:2 (Spring)
Offered this year?No
When Offered?Every year


Introduction to serial and parallel models of computation; time and space complexity classes on these models; the circuit model of computation and its relation to serial and parallel time complexity; space-time tradeoffs on serial computers; area-time tradeoffs on the VLSI computational model; interactive and probabilistically checkable proofs; the definition of NP in terms of probabilistically checkable proofs; hardness of approximations to solutions to NP-hard problems. Prerequisite: CSCI 0510.

CRN: None