Undergraduate Complexity Theory
Undergraduate Complexity Theory
Undergraduate Complexity Theory
Undergraduate Complexity Theory
Undergraduate Complexity Theory
Welcome to CS455 at CMU!
Complexity theory is the study of how much of a resource (such as time, space, parallelism, or randomness) is required to perform some of the computations that interest us the most. In a standard algorithms course, one concentrates on giving resource efficient methods to solve interesting problems. In this course, we concentrate on techniques that prove or suggest that there are no efficient methods to solve many important problems. We will develop the theory of various complexity classes. We will study techniques to classify problems according to our available taxonomy. By developing a subtle pattern of reductions between classes we will suggest an (as yet unproven!) picture of how by using limited amounts of various resources, we limit our computational power.
The main goal of the study of computational complexity theory is understanding, for a given computational task, what is the most efficient way of solving it. Efficiency can be measured with respect to various resources. This course will mainly focus on time and space/memory as resources, and in this module, we start with time complexity.
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.