Complexity and Computational Models

Catalog description

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 theminimal 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.