CSCI1590

(Formerly CS159 )

Introduction to Computational Complexity

Instructor(s):
Course Home Page:
http://www.cs.brown.edu/courses/csci1590/
Offered This Year?  No
When Offered? Every Other Year

Description

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.