Computational Complexity

4.0 credits

This course is based on doing hands-on problem-solving to uncover the power and limitations of computer algorithms, and in particular focuses on in-class, group, discovery-based learning. This is usually done via the class's members creating algorithms under situation-specific assumptions, as much of complexity theory is based on simple algorithms. If you secretly liked 280 or 282, but would enjoy moving forward in a much smaller setting where you work with a few teammates to solve challenges and discover/design algorithms, this course likely is for you. The course typically covers the following: 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?; characterizing whether one-way functions exist; reductions relating problems' complexities; complexity classes and hierarchies.