Computability and Complexity Classes

Computability and the fundamental time-based complexity classes (P, NP, and their relatives) answer two questions: can a problem be solved by a mechanical procedure at all, and if so, how fast? This material is relevant whenever you must establish whether a problem is tractable before committing engineering effort, or when you need to prove that no polynomial-time algorithm exists for a given decision problem.

Authoritative sources

On Computable Numbers, with an Application to the Entscheidungsproblem

Computers and Intractability: A Guide to the Theory of NP-Completeness

The Complexity of Theorem-Proving Procedures (Cook, 1971)

Reducibility Among Combinatorial Problems (Karp, 1972)

Turing machines

A Turing machine $M = (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$ is a 7-tuple where $Q$ is a finite set of states, $\Sigma$ is the input alphabet, $\Gamma$ is the tape alphabet ( $\Sigma \subseteq \Gamma$ ), $\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$ is the transition function, and $q_0, q_{accept}, q_{reject} \in Q$ are special states.

A language $L \subseteq \Sigma^*$ is decidable (recursive) if some Turing machine halts on every input and accepts exactly the strings in $L$ .

Details

The Church–Turing thesis asserts that any effectively computable function can be computed by a Turing machine. This makes the Turing machine the universal model of computation: RAM machines, lambda calculus, and recursive functions all compute exactly the same class of functions.

The halting problem asks: given a description of a Turing machine $M$ and input $w$ , does $M(w)$ halt? Turing proved this is undecidable by diagonalization: if a decider $H$ existed, one could construct a machine $D$ that does the opposite of $H(D, D)$ , a contradiction.

Key consequences:

No program can perfectly predict whether another program will terminate.
No compiler can detect all infinite loops.
The set of undecidable languages is uncountable (there are countably many machines but uncountably many languages).

Try the interactive simulator below: it runs a two-state Turing machine that decides whether the number of 1s on the tape is even. Load it, then step through the tape cell by cell and watch the head move and the state toggle between “even” and “odd”.

Example problem: design a Turing machine deciding $L = \{w \in \{0,1\}^* : w \text{ contains an even number of } 1\text{s}\}$ .

Solution

Use two states: $q_{even}$ (start state, also accepting) and $q_{odd}$ . The transition function is:

$\delta(q_{even}, 1) = (q_{odd}, 1, R)$ and $\delta(q_{odd}, 1) = (q_{even}, 1, R)$ — each 1 toggles the parity.
$\delta(q_{even}, 0) = (q_{even}, 0, R)$ and $\delta(q_{odd}, 0) = (q_{odd}, 0, R)$ — 0s leave the parity unchanged.
On the blank symbol $\sqcup$ : $\delta(q_{even}, \sqcup) = q_{accept}$ and $\delta(q_{odd}, \sqcup) = q_{reject}$ .

The machine scans left to right once, so it runs in $O(n)$ time and uses $O(n)$ tape cells: parity is a regular, linear-time-decidable property. The same “finite memory swept across the input” pattern underlies many deciders; richer languages (like balanced parentheses) need the full tape as a counter or stack instead.

Once we have a formal model of computation, the natural next question is: how much time or space does the machine need? This question gives rise to the complexity classes below.

Complexity classes

A language $L$ is in P if a deterministic Turing machine decides it in $O(n^k)$ time for some constant $k$ . A language is in NP if a nondeterministic Turing machine decides it in polynomial time, equivalently if every “yes” instance has a polynomial-length certificate verifiable in polynomial time.

BPP (Bounded-error Probabilistic Polynomial time): a probabilistic Turing machine decides in polynomial time with error probability $< 1/3$ on every input. The constant $1/3$ is arbitrary: by running the machine $O(\log(1/\varepsilon))$ times and taking a majority vote, the error can be reduced to any desired $\varepsilon > 0$ while staying polynomial time (this is amplification).

BQP (Bounded-error Quantum Polynomial time): the quantum analogue of BPP, decided by a quantum circuit of polynomial depth. $\text{BPP} \subseteq \text{BQP} \subseteq \text{PSPACE}$ (both inclusions proven; Bernstein–Vazirani 1997 for $\text{BQP} \subseteq \text{PSPACE}$ ); whether $\text{BQP} \subseteq \text{P}$ is open. See Quantum Mechanics.

PSPACE: languages decidable by a deterministic Turing machine using $O(n^k)$ tape space for some constant $k$ , regardless of time. Since a polynomial-space machine has only polynomially many configurations, it can be simulated in exponential time, which gives $\text{P} \subseteq \text{NP} \subseteq \text{PH} \subseteq \text{PSPACE}$ .

co-NP: the class of complements of NP languages — languages whose “no” instances have polynomially checkable certificates. It is unknown whether $\text{NP} = \text{co}\text{-NP}$ ; if they differ, no NP-complete problem can have a short proof for its “no” instances.

Polynomial Hierarchy (PH): generalizes NP and co-NP via oracle machines (or alternating TMs). $\text{NP} \subseteq \text{PH} \subseteq \text{PSPACE}$ . PH is the natural next step after P and NP and is relevant to inapproximability results.

See Space and Parallel Complexity for space complexity classes (L, NL, PSPACE, EXPSPACE), hierarchy theorems, and circuit complexity (NC, AC⁰) in detail.

Details

Hierarchy of complexity classes

Cook–Levin and NP-completeness

The Cook–Levin theorem (Cook, 1971; Levin, 1973) establishes that SAT is NP-complete: every problem in NP polynomial-time reduces to SAT. Karp (1972) showed 21 combinatorial problems are NP-complete, including 3-SAT, CLIQUE, VERTEX-COVER, HAMILTONIAN CYCLE, and PARTITION.

Reduction: $A \le_p B$ means there is a polynomial-time computable function $f$ such that $x \in A \iff f(x) \in B$ . If $A$ is NP-complete and $A \le_p B$ , then $B$ is NP-hard.

Worked example: 3-SAT ≤ₚ CLIQUE

Take the formula $\varphi = (x_1 \lor \lnot x_2 \lor x_3) \land (\lnot x_1 \lor x_2 \lor x_3)$ .

Step 1 — Create one vertex per literal per clause:

Clause 1: $v_1 = x_1$ , $v_2 = \lnot x_2$ , $v_3 = x_3$
Clause 2: $v_4 = \lnot x_1$ , $v_5 = x_2$ , $v_6 = x_3$

Step 2 — Connect two vertices with an edge iff they are from different clauses AND are not complementary (i.e., one is not the negation of the other).

Step 3 — The graph has a clique of size 2 (= number of clauses) iff $\varphi$ is satisfiable.

The clique $\{x_1, x_3\}$ (one vertex from each clause, connected by an edge) corresponds to the satisfying assignment $x_1 = T, x_3 = T$ .

PCP theorem

The PCP theorem (Arora, Lund, Motwani, Sudan, Szegedy, 1998) states that $\text{NP} = \text{PCP}(O(\log n), O(1))$ : every NP language has a probabilistically checkable proof where the verifier reads only $O(1)$ bits of the proof and uses $O(\log n)$ random bits. This is the foundation of inapproximability results: for example, MAX-3SAT is not approximable within $7/8 + \varepsilon$ unless $\text{P} = \text{NP}$ (Håstad, 1997).

Authoritative sources

PCP theorem paper (Arora et al., 1998)

The hardness of approximation (Håstad, 1997)

Practical implications

NP-complete problems have no known polynomial-time algorithm.
Heuristics, approximation algorithms, and parameterized algorithms are the standard tools (see Graphs for Christofides’ approximation for TSP, and Optimization and Differentiation for continuous optimization).
In practice, many NP-complete instances are easy; hardness is worst-case.

Example problem: show that the language $L = \{w \in \{0,1\}^* : w \text{ has an even number of } 1\text{s}\}$ is in P.

Solution

A one-pass algorithm decides $L$ in linear time: initialize a bit $p = 0$ ; scan the input left to right, and whenever the current symbol is 1, flip $p$ ( $p \leftarrow 1 - p$ ); when the scan ends, accept iff $p = 0$ . Flipping a bit is exactly addition modulo 2, so $p$ tracks the parity of the number of 1s seen so far. The scan performs $n$ symbol inspections and at most $n$ bit flips, which is $O(n)$ time and $O(1)$ extra space — polynomial, so $L \in \text{P}$ . (In fact $L$ is regular and even decidable by a two-state finite automaton, which is the machine drawn in the simulator above.)

Open problems

Complexity theory still has famous unresolved questions — statements about whether two of these classes coincide, where decades of research have settled only one direction of the inclusion:

P vs NP: can every efficiently verifiable certificate also be found efficiently? The most famous open problem in computer science, and one of the Clay Millennium Prize problems.
NP vs co-NP: whether “no” instances of NP problems also have short certificates. P = NP would imply NP = co-NP, but the converse is open.
BPP vs P: whether randomness adds power. BPP ⊆ PSPACE is proven, BPP ⊆ P is open, and most researchers conjecture BPP = P.
BQP vs NP: whether quantum computers can efficiently solve NP-complete problems. BQP ⊆ PSPACE is proven; BQP vs NP is open.

Details

These questions form the lattice of inclusions drawn in the hierarchy diagram above: for each pair of classes, one inclusion is a theorem and the reverse inclusion is open. They are deeply entangled: proving P = NP would collapse the entire polynomial hierarchy PH down to P, and proving BPP = P would show that randomness never helps for decision problems. This is why unconditional results such as the PCP theorem and the inapproximability bounds above are so valuable — they hold regardless of how these open questions resolve.

Quizz

Problem: Show that SAT ≤ₚ 3-SAT: given a CNF formula $\varphi$ whose clauses may have any length, build in polynomial time a 3-CNF formula $\varphi'$ that is satisfiable exactly when $\varphi$ is.

Solution

Construction. Process each clause $C = (\ell_1 \lor \ell_2 \lor \cdots \lor \ell_k)$ independently, using fresh variables $z_1, \dots, z_{k-3}$ that appear nowhere else:

$k = 1$ : replace $\ell_1$ by $(\ell_1 \lor z) \land (\ell_1 \lor \lnot z)$ for a fresh $z$ — the two clauses together force $\ell_1$ to be true.
$k = 2$ : keep $(\ell_1 \lor \ell_2)$ as is.
$k \ge 3$ : replace $C$ by the chain $(\ell_1 \lor \ell_2 \lor z_1) \land (\lnot z_1 \lor \ell_3 \lor z_2) \land \cdots \land (\lnot z_{k-3} \lor \ell_{k-1} \lor \ell_k)$ .

Correctness. If an assignment satisfies $C$ , some $\ell_j$ is true; set the $z_i$ before $j$ to make each earlier clause true via its $\lnot z$ literal, and the clause containing $\ell_j$ is satisfied by $\ell_j$ itself. Conversely, restrict any satisfying assignment of the chain to the original variables: if all $\ell_j$ were false, the first clause forces $z_1$ true, the second forces $z_2$ true, …, and the last clause $(\lnot z_{k-3} \lor \ell_{k-1} \lor \ell_k)$ would be false — a contradiction. So $\varphi'$ is satisfiable iff $\varphi$ is.

Polynomial time. A clause of length $k$ becomes $\max(1, k-2)$ clauses of size ≤ 3, so $|\varphi'| = O(|\varphi|)$ and the construction is linear time.

This is the reverse direction of the worked example above: together, SAT ≤ₚ 3-SAT and 3-SAT ≤ₚ CLIQUE show that SAT, 3-SAT, and CLIQUE are all NP-complete as hard as each other.

Computability and Complexity Classes §

Turing machines §

Complexity classes §

Hierarchy of complexity classes §

Cook–Levin and NP-completeness §

Worked example: 3-SAT ≤ₚ CLIQUE §

PCP theorem §

Practical implications §

Open problems §

Quizz §

Computability and Complexity Classes

Turing machines

Complexity classes

Hierarchy of complexity classes

Cook–Levin and NP-completeness

Worked example: 3-SAT ≤ₚ CLIQUE

PCP theorem

Practical implications

Open problems

Quizz