Computational Complexity Theory

This document collects the basic definitions of computational complexity theory: models of computation, decision problems, asymptotic notation, the standard time and space complexity classes, reductions, and the elementary completeness and hierarchy results. It is a self-contained reference; for a real treatment see Sipser, Introduction to the Theory of Computation; Arora & Barak, Computational Complexity: A Modern Approach; Papadimitriou, Computational Complexity.

Unlike the other math notes in this folder, complexity theory is independent of the topology / group-theory / Clifford-algebra chain — it can be read on its own.

1. Models of Computation

1.1 Turing machines

A (deterministic, one-tape) Turing machine is a tuple $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,q_{\text{acc}},q_{\text{rej}})$ where

• $Q$ is a finite set of states,
• $\Sigma$ is the input alphabet, $\Gamma \supseteq \Sigma \cup \{\bigsqcup \}$ the tape alphabet (with blank $\bigsqcup$),
• $\delta :Q\times \Gamma \to Q\times \Gamma \times \{L,R\}$ is the transition function,
• $q_0\in Q$ is the start state, and $q_{\text{acc}},q_{\text{rej}}\in Q$ are the accepting / rejecting halt states.

On input $x\in {\Sigma }^{\ast }$, $M$ starts in state $q_0$ with $x$ written on the tape and the head at the leftmost cell. At each step it reads the current cell, writes a new symbol, moves the head left or right, and transitions to a new state according to $\delta$. $M$ halts when it enters $q_{\text{acc}}$ (accepts) or $q_{\text{rej}}$ (rejects). The running time $t_M(x)$ is the number of steps before halting; the space $s_M(x)$ is the number of distinct tape cells visited.

Variants — multi-tape machines, two-way tapes, RAM machines, $\lambda$-calculus, etc. — all simulate one another with at most polynomial overhead, so the class of polynomial-time problems is robust under choice of model. This is the invariance thesis (a stronger, machine-relative form of the Church–Turing thesis).

1.2 Nondeterministic Turing machines

A nondeterministic Turing machine (NTM) replaces $\delta$ with a relation $\delta \subseteq (Q\times \Gamma )\times (Q\times \Gamma \times \{L,R\})$: from a given configuration there may be several legal next moves. An NTM accepts $x$ if some sequence of nondeterministic choices leads to $q_{\text{acc}}$. The running time is the length of the shortest accepting computation (or, on rejection, the maximum over all branches).

Equivalent formulations:

• a deterministic verifier $V(x,w)$ that checks a certificate (witness) $w$ of length polynomial in $|x|$,
• a deterministic machine equipped with a "guess" oracle.

Nondeterminism is not a physical model — no known device computes faster by branching exponentially — but it is the cleanest mathematical handle on search problems.

1.3 Other models

• Boolean circuits: families $\{C_n{\}}_{n\in \mathbb{N}}$ of acyclic directed graphs over $\{\wedge ,\vee ,\neg \}$ with $n$ input wires; gives non-uniform complexity (one circuit per input length). See § 8.
• Randomized Turing machines: $\delta$ has access to fair coin flips; the machine accepts with some probability. See § 7.
• Quantum Turing machines / quantum circuits: unitary evolution on a Hilbert space of qubits, with measurement at the end. The associated class is $\mathsf{BQP}$ — see the qcfront project for hands-on quantum computing.

2. Decision Problems, Languages, and Promise Problems

A language is a subset $L\subseteq {\Sigma }^{\ast }$ of strings over a finite alphabet (typically $\Sigma =\{0,1\}$). A decision problem is the question "given $x$, is $x\in L$?" Examples:

• $\mathrm{PRIMES}=\{⟨n⟩:n\text{ is prime}\}$,
• $\mathrm{SAT}=\{⟨\phi ⟩:\phi \text{ is a satisfiable Boolean formula}\}$,
• $\mathrm{HAMPATH}=\{⟨G,s,t⟩:G\text{ has a Hamiltonian }s\text{-}t\text{ path}\}$.

A Turing machine $M$ decides $L$ if $M$ halts on every input and accepts exactly the strings in $L$.

Function problems ("compute $f(x)$") and search problems ("find a witness") are reducible to and from decision problems for the natural classes; we work with decision problems for cleanliness. A promise problem is a pair $(L_{\text{yes}},L_{\text{no}})$ of disjoint sets, with the machine's behavior on ${\Sigma }^{\ast }\setminus (L_{\text{yes}}\cup L_{\text{no}})$ unconstrained — useful for $\mathsf{BPP}$-style classes.

3. Asymptotic Notation

Let $f,g:\mathbb{N}\to {\mathbb{R}}_{\ge 0}$. Then

The "$=$" in "$f=O(g)$" is conventional abuse of notation; it really means $f\in O(g)$ (a set).

Polynomial / exponential growth. "$f$ is polynomial" means $f(n)=O(n^k)$ for some constant $k$. "$f$ is exponential" usually means $f(n)=2^{O(n^k)}$ for some $k$; "polylogarithmic" means $(\log n{)}^{O(1)}$. The catch-all $\mathrm{poly}(n)$ denotes any polynomial in $n$.

4. Time and Space Complexity Classes

For a function $f:\mathbb{N}\to \mathbb{N}$, define

$$\begin{array}{rl}\mathsf{DTIME}(f(n))& \equiv \{L:\exists \text{deterministic TM deciding }L\text{ in time }O(f(n))\},\\ \mathsf{NTIME}(f(n))& \equiv \{L:\exists \text{nondeterministic TM deciding }L\text{ in time }O(f(n))\},\\ \mathsf{DSPACE}(f(n))& \equiv \{L:\exists \text{det. TM deciding }L\text{ in space }O(f(n))\},\\ \mathsf{NSPACE}(f(n))& \equiv \{L:\exists \text{nondet. TM deciding }L\text{ in space }O(f(n))\}.\end{array}$$

For space, the input is on a read-only tape and only the work tape is counted (this is what makes sublinear-space classes meaningful).

4.1 The standard classes

The Cobham–Edmonds thesis identifies $\mathsf{P}$ with the feasibly computable problems — a reasonable working hypothesis, although large constants and exponents can defeat polynomial running times in practice.

4.2 NP via verifiers

Equivalent definition of $\mathsf{NP}$: $L\in \mathsf{NP}$ iff there exist a deterministic polynomial-time machine $V$ (the verifier) and a polynomial $p$ such that

$$x\in L⟺\exists w\in \{0,1{\}}^{p(|x|)}\text{such that}V(x,w)=1.$$

The witness $w$ is a certificate for $x$. This is the operational definition usually used in practice: showing $L\in \mathsf{NP}$ amounts to exhibiting a short, efficiently-checkable proof of membership.

5. Inclusions and Separations

The following inclusions are unconditional:

$$\mathsf{L}\subseteq \mathsf{NL}\subseteq \mathsf{P}\subseteq \mathsf{NP}\subseteq \mathsf{PSPACE}\subseteq \mathsf{EXPTIME}\subseteq \mathsf{NEXPTIME}\subseteq \mathsf{EXPSPACE}.$$

Known to be proper: $\mathsf{NL}⊊\mathsf{PSPACE}$, $\mathsf{P}⊊\mathsf{EXPTIME}$, $\mathsf{NP}⊊\mathsf{NEXPTIME}$, $\mathsf{PSPACE}⊊\mathsf{EXPSPACE}$ (all follow from the hierarchy theorems, § 9). It is therefore known that at least one of the inclusions $\mathsf{P}\subseteq \mathsf{NP}\subseteq \mathsf{PSPACE}\subseteq \mathsf{EXPTIME}$ is strict — we just don't know which one(s).

Open (the headliners):

• $\mathsf{P}\stackrel{?}{=}\mathsf{NP}$ — the central open problem of theoretical CS; a Clay Millennium Prize Problem.
• $\mathsf{NP}\stackrel{?}{=}\mathsf{coNP}$.
• $\mathsf{L}\stackrel{?}{=}\mathsf{P}$, $\mathsf{L}\stackrel{?}{=}\mathsf{NL}$.
• $\mathsf{P}\stackrel{?}{=}\mathsf{PSPACE}$.

Two structural theorems worth remembering:

• Savitch's theorem (1970): $\mathsf{NSPACE}(f(n))\subseteq \mathsf{DSPACE}(f(n{)}^2)$ for $f(n)\ge \log n$. Consequence: $\mathsf{PSPACE}=\mathsf{NPSPACE}$, $\mathsf{EXPSPACE}=\mathsf{NEXPSPACE}$ — nondeterminism gives at most a quadratic space saving.
• Immerman–Szelepcsényi theorem (1987–88): $\mathsf{NSPACE}(f(n))=\mathrm{co}\mathsf{NSPACE}(f(n))$ for $f(n)\ge \log n$. In particular $\mathsf{NL}=\mathrm{co}\mathsf{NL}$ — nondeterministic space classes are closed under complement, in striking contrast to the conjectured $\mathsf{NP}\ne \mathsf{coNP}$.

6. Reductions and Completeness

To compare difficulty across problems we use reductions.

6.1 Polynomial-time many-one (Karp) reductions

$A{\le }_{p}B$ iff there exists a polynomial-time computable function $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ such that

$$x\in A⟺f(x)\in B.$$

In words: $A$ instances are translated to equivalent $B$ instances. If $B\in \mathsf{P}$ and $A{\le }_{p}B$, then $A\in \mathsf{P}$. ${\le }_p$ is reflexive and transitive.

6.2 Polynomial-time Turing (Cook) reductions

$A{\le }_T^{p}B$ iff $A$ is decidable in polynomial time by a Turing machine with oracle access to $B$ (a constant-time membership query for $B$). Cook reductions are at least as powerful as Karp reductions (every Karp reduction is a one-query Cook reduction). The distinction matters for asymmetric classes like $\mathsf{NP}$ vs $\mathsf{coNP}$ — Karp reductions preserve "yes-instances of $\mathsf{NP}$" while Cook reductions need not.

6.3 Completeness

For a class $\mathcal{C}$ and a reduction $\le$,

• $L$ is $\mathcal{C}$-hard (under $\le$) if every $A\in \mathcal{C}$ satisfies $A\le L$.
• $L$ is $\mathcal{C}$-complete if it is $\mathcal{C}$-hard and $L\in \mathcal{C}$.

A $\mathcal{C}$-complete problem is "the hardest problem in $\mathcal{C}$": placing it in any sub-class ${\mathcal{C}}^{\prime }$ (closed under the reduction) would collapse $\mathcal{C}\subseteq {\mathcal{C}}^{\prime }$.

6.4 The Cook–Levin theorem and NP-completeness

Cook–Levin theorem (1971, independently Levin): $\mathrm{SAT}$ is $\mathsf{NP}$-complete under polynomial-time many-one reductions. The proof encodes the computation tableau of an arbitrary polynomial-time NTM as a Boolean formula whose satisfying assignments correspond to accepting computations.

Karp (1972) used this as a seed to show $\mathsf{NP}$-completeness of 21 natural problems, and the list has since grown to thousands. A small sampler:

Practical upshot: if you can reduce one of these to your problem, your problem is at least as hard as $\mathrm{SAT}$, and (assuming $\mathsf{P}\ne \mathsf{NP}$) admits no polynomial-time algorithm.

6.5 Completeness for other classes

7. The Polynomial Hierarchy

Generalize $\mathsf{NP}$ (one existential quantifier over a poly-bounded witness) and $\mathsf{coNP}$ (one universal) by allowing alternations:

$$\begin{array}{rl}{\Sigma }_0^p& ={\Pi }_0^p={\Delta }_0^p=\mathsf{P},\\ {\Sigma }_{k+1}^p& ={\mathsf{NP}}^{{\Sigma }_k^p},{\Pi }_{k+1}^p={\mathsf{coNP}}^{{\Sigma }_k^p},{\Delta }_{k+1}^p={\mathsf{P}}^{{\Sigma }_k^p},\end{array}$$

where ${\mathcal{C}}^{\mathcal{D}}$ denotes class $\mathcal{C}$ with oracle access to $\mathcal{D}$. Equivalently, $L\in {\Sigma }_k^p$ iff there exists a poly-time predicate $R$ and a polynomial $p$ such that

$$x\in L⟺\exists w_1\forall w_2\exists w_3\cdots Q_k{w}_{k}R(x,w_1,\dots ,w_k),$$

with $|w_i|\le p(|x|)$ and $Q_k=\exists$ for $k$ odd, $\forall$ for $k$ even. The union

$$\mathsf{PH}\equiv \bigcup _{k\ge 0}{\Sigma }_k^p$$

is the polynomial hierarchy. We have $\mathsf{PH}\subseteq \mathsf{PSPACE}$; whether the hierarchy is infinite or collapses at some level is open. Collapses propagate upward: if ${\Sigma }_k^p={\Pi }_k^p$ for any $k$, then $\mathsf{PH}={\Sigma }_k^p$. In particular $\mathsf{P}=\mathsf{NP}$ would collapse the entire hierarchy to $\mathsf{P}$.

8. Randomized and Non-Uniform Classes

8.1 Randomized polynomial time

A probabilistic Turing machine runs in polynomial time and has access to random bits.

The probability gap is amplified by repetition: a polynomial number of independent trials drives the error to $2^{-\mathrm{poly}(n)}$ (Chernoff bound). Inclusions: $\mathsf{P}\subseteq \mathsf{ZPP}\subseteq \mathsf{RP}\subseteq \mathsf{BPP}\subseteq \mathsf{PP}\subseteq \mathsf{PSPACE}$; also $\mathsf{BPP}\subseteq {\Sigma }_2^p\cap {\Pi }_2^p$ (Sipser–Gács–Lautemann). It is widely conjectured (and supported by derandomization results based on circuit lower bounds) that $\mathsf{BPP}=\mathsf{P}$.

8.2 Boolean circuits and $P/poly$

A circuit family $\{C_n\}$ decides $L$ if $C_n$ has $n$ inputs and $C_n(x)=1⟺x\in L$ for all $x\in \{0,1{\}}^n$. The complexity of a family is measured by size $|C_n|$ (gate count) and depth $d(C_n)$ (longest input-to-output path).

• $P/poly$: languages decided by polynomial-size circuit families (no uniformity required). $\mathsf{P}\subseteq P/poly$, and $\mathsf{BPP}\subseteq P/poly$ (Adleman). But $P/poly$ contains undecidable languages — non-uniformity is genuinely more powerful.
• ${\mathsf{AC}}^k$: poly-size, depth $O({\log }^{k}n)$, unbounded-fan-in $\wedge /\vee$ gates.
• ${\mathsf{NC}}^k$: poly-size, depth $O({\log }^{k}n)$, bounded-fan-in gates. $\mathsf{NC}\equiv {\bigcup }_k{\mathsf{NC}}^k$ is "efficiently parallelizable".
• Chain: ${\mathsf{NC}}^0\subseteq {\mathsf{AC}}^0\subseteq {\mathsf{NC}}^1\subseteq \mathsf{L}\subseteq \mathsf{NL}\subseteq {\mathsf{NC}}^2\subseteq \cdots \subseteq \mathsf{NC}\subseteq \mathsf{P}$.

The conjecture $\mathsf{NP}⊈P/poly$ would imply $\mathsf{P}\ne \mathsf{NP}$, and is the basis for the circuit-lower-bound approach to separation. (Karp–Lipton: if $\mathsf{NP}\subseteq P/poly$, then $\mathsf{PH}={\Sigma }_2^p$.)

8.3 Quantum polynomial time

$\mathsf{BQP}$ is the class of languages decided with bounded error by a polynomial-size family of uniform quantum circuits. Known: $\mathsf{BPP}\subseteq \mathsf{BQP}\subseteq \mathsf{PSPACE}$; relationship of $\mathsf{BQP}$ to $\mathsf{NP}$ is open. Shor's factoring algorithm places $\mathrm{FACTORING}$ in $\mathsf{BQP}$; this is conjectured to be outside $\mathsf{P}$ but not known to be $\mathsf{NP}$-complete. See misc/quantum-complexity-theory.md for the full quantum-complexity story (models of quantum computation, $\mathsf{EQP}$ / $\mathsf{QMA}$ / $\mathsf{QIP}$, oracle separations, local Hamiltonian completeness) and qcfront for hands-on quantum-computing code.

9. Hierarchy Theorems

The hierarchy theorems formalize "more resource = more power". A function $f:\mathbb{N}\to \mathbb{N}$ is time-constructible if some TM, given input $1^n$, outputs $f(n)$ in time $O(f(n))$; space-constructible is the analogous notion for space. All "reasonable" functions ($n^k$, $2^n$, $n\log n$, …) are constructible.

Time hierarchy theorem (Hartmanis–Stearns, 1965). If $f,g$ are time-constructible and $f(n)\log f(n)=o(g(n))$, then

$$\mathsf{DTIME}(f(n))⊊\mathsf{DTIME}(g(n)).$$

Space hierarchy theorem. If $f,g$ are space-constructible and $f(n)=o(g(n))$ (with $g(n)\ge \log n$), then

$$\mathsf{DSPACE}(f(n))⊊\mathsf{DSPACE}(g(n)).$$

Both proofs go via diagonalization: build a machine that, given $⟨M,x⟩$, simulates $M$ on $x$ for $g(n)$ steps (or cells) and flips the answer. Corollaries already used in § 5: $\mathsf{P}⊊\mathsf{EXPTIME}$, $\mathsf{PSPACE}⊊\mathsf{EXPSPACE}$, $\mathsf{NP}⊊\mathsf{NEXPTIME}$.

These are essentially the only general-purpose tools known for proving lower bounds on uniform machines. Pure diagonalization cannot resolve $\mathsf{P}\stackrel{?}{=}\mathsf{NP}$ — the relativization barrier (Baker–Gill–Solovay, 1975) shows that there exist oracles $A,B$ with ${\mathsf{P}}^A={\mathsf{NP}}^A$ and ${\mathsf{P}}^B\ne {\mathsf{NP}}^B$, so any proof technique that relativizes (as diagonalization does) cannot decide the question. Subsequent barriers — natural proofs (Razborov–Rudich, 1994) and algebrization (Aaronson–Wigderson, 2008) — rule out further large classes of techniques.

10. Beyond the Basics (Pointers)

A non-exhaustive map of where complexity theory goes from here:

• Approximation and hardness of approximation. Many $\mathsf{NP}$-hard optimization problems admit good polynomial-time approximation algorithms; the PCP theorem (Arora–Lund–Motwani–Sudan–Szegedy, 1992–98) characterizes $\mathsf{NP}$ via probabilistically checkable proofs and gives tight inapproximability results.
• Interactive proofs. $\mathsf{IP}$ — languages decidable by a polynomial-time verifier interacting with an all-powerful prover — equals $\mathsf{PSPACE}$ (Shamir, 1992). Multi-prover variants: $\mathsf{MIP}=\mathsf{NEXPTIME}$.
• Average-case complexity (Levin, 1986): hardness against random instances, foundational for cryptography.
• Communication complexity, query complexity, proof complexity, fine-grained complexity (e.g. SETH-based lower bounds within $\mathsf{P}$), descriptive complexity (Fagin's theorem: $\mathsf{NP}=$ existential second-order logic).
• Cryptographic assumptions (one-way functions, trapdoor permutations, LWE) sit above $\mathsf{P}\ne \mathsf{NP}$ in strength — they encode worst-case-to-average-case structure that is conjectured but unproved.

See Arora & Barak, Computational Complexity: A Modern Approach, for systematic treatments of all of the above.