Two fundamental questions arising in any problem are: Can this problem be solved using a given abstract machine? How much time and space are required to solve it? The theory of computational complexity provides tools for analyzing the minimal amount of computational resources that are needed for the algorithmic solution of a problem. In this course we will discuss a variety of types of computational problems (decision, search, counting and optimization) by introducing an array of complexity classes to capture problem types. We will use the notions of reduction and completeness to establish relationships between seemingly unrelated problems, classes, and resources.
Prerequisites: MTH 3150 and MTH 4320.
Apply to this course