Fundamental Results

Polynomial Time

Cook-Levin Theorem

Smalll Space

Polynomial Hierarchy

Probabilistic Classes

Reversible Computation

Turing Machines

Completeness

Nondeterminism

Ladner's Theorem

Counting

Randomness

Circuit Complexity

Complexity Theory

Hardness

Satisfiabilty

Karp's List

Polynomial Space

Kolmogorov complexity

Interactive Proofs

Hypercomputation

Computability

Time Complexity

P/NP

Space Complexity

Immerman–Szelepcsényi theorem

Randomized Algorithms

Descriptive complexity theory

15-455 Undergraduate Complexity Theory Carnegie Mellon University Spring 2023 This course provides an initial dive into complexity theory, exploring computations bound by resources like time, space, and energy. Emphasis is placed on low complexity classes.  This course provides a gentle introduction into complexity theory, the theory of computations that are restricted by various resource bounds (time, space, energy, ...). We start with a brief tour of the computational universe at large and then home in on the low complexity classes that are most relevant in theoretical computer science such as P, NP, PSPACE. LOG,NLOG, BPP, RP and circuit-based classes.   

15-455 Undergraduate Complexity Theory

Theoretical Computer Science

Fundamental Results

1 courses cover this concept

15-455 Undergraduate Complexity Theory