CSCI1590
(Formerly
CS159
)
Introduction to Computational Complexity
| 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.
|
Page Owner: webmaster
|
Last Modified: Mon Oct 19 09:49:39 2009
|
