CSC 286/486: Computational Complexity

Fall 2008 Information

This course studies the difference between computable and uncomputable problems, and also, especially, studies the difference between feasible and infeasible problems. What properties of a problem make it computationally simple? What properties of a problem may preclude its having efficient algorithms? How computationally hard are problems? Complete sets and low information content; P=NP?; unambiguous computation, one-way functions, and cryptography; reductions relating the complexity of problems; complexity classes and hierarchies.

Students taking this course at the 400 level may be required to complete additional tests, readings, or assignments.

Prerequisite: CSC 280; CSC 282 is co-requisite. (Fall.)


Last updated 10/1/2008 by Marty Guenther (marty@cs.rochester.edu)