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.