CSCI1590
(Formerly CS159)Introduction to Computational Complexity
Not offered this yearOffered discontinued, last taught:
Spring 2019
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.
Instructor(s): | |
CRN: | None |