Cook-Levin Theorem

Regular Languages

Pumping Lemma

Pumping lemma for context-free languages

Undecidability

Rice’s Theorem

Turing Reducibility

Polynomial Time

Space Complexity

Regular Operations

Push-Down Automata

Chomsky Normal Form

Mapping Reducibilities

Fixed-point theorem

P=NP

Savitch's Theorem

Kolmogorov complexity

Non-determinism

Minimizing DFA

Equivalence of PDAs and CFGs

Reductions

Recursion theorem

The Arithmetic Hierarchy

Non-Deterministic Turning Machines

Karp

Polynomial identity testing

Deterministic Finite Automata

Regular Expressions

Context-Free Grammars

Turing Machines

Post Correspondence Problem

Oracle Turing Machines

Time Complexity

NP-completeness

PSPACE-Completeness

15-453 - Formal Languages, Automata, and Computability Carnegie Mellon University Spring 2015 A foundational course that introduces formal languages, automata, computability, and complexity theories, including finite automata, Turing machines, and P/NP classes.  This course provides an introduction to formal languages, automata, computability, and complexity. The course consists of a traditional lecture component supported by weekly homework assignments and quizzes and a course project. There are two midterms and a final examination.

### Topics

- **Automata and Languages**: finite automata, regular languages, pushdown automata, context-free languages, pumping lemmas.
- **Computability Theory**: Turing Machines, decidability, reducibility, the arithmetic hierarchy the recursion theorem, the Post correspondence problem.
- **Complexity Theory**: time complexity, classes P and NP, NP-completeness, space complexity, PSPACE, PSPACE-completeness, the polynomial hierarchy, randomized complexity, classes RP and BPP.  15-251 or 21-228. Textbook: Introduction to the Theory of Computation (3rd Ed.) by Michael Sipser, 2012.
Errata for 3rd Edition: http://math.mit.edu/~sipser/itoc-derrs3.1.html

15-453 - Formal Languages, Automata, and Computability

Theoretical Computer Science

Fundamental Results

Smalll Space

Polynomial Hierarchy

Probabilistic Classes

Reversible Computation

Completeness

Nondeterminism

Ladner's Theorem

Counting

Randomness

Circuit Complexity

Complexity Theory

Hardness

Satisfiabilty

Karp's List

Polynomial Space

Interactive Proofs

Hypercomputation

Computability

P/NP

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

Cook%E2%80%93Levin theorem

Cook-Levin Theorem

2 courses cover this concept

15-453 - Formal Languages, Automata, and Computability

15-455 Undergraduate Complexity Theory