CSC 286: Computational Complexity

CRN:
36079
Credit Hours:
4.0
Previous Offerings:

The difference between computable and uncomputable problems and between feasible and infeasible problems.  Regarding the latter, 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.