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)