Foundations of Computation Theory

This section introduces the basics of computability and complexity theory. These topics are not very important in OI (though they are still somewhat useful: if you encounter an NP-hard problem, you may assume that no polynomial-time solution exists), so you can read them out of interest or as preparation for later study.

Many conclusions in this article are stated without proof; if you are interested, you can look up the relevant proofs yourself.

Prerequisite knowledge: time complexity.

Problems

Languages

An alphabet is a nonempty finite set whose elements are called symbols/characters.

Let $\Sigma^\ast$ denote the strings formed by concatenating a nonnegative number of characters from $\Sigma$. A language over the alphabet $\Sigma$ is a subset of $\Sigma^\ast$.

Note that “language” here is an abstract concept. Ordinary strings form a language, and the set of all directed acyclic graphs can also be a language (a bijection can be established between binary strings and directed graphs; the details are not needed here).

Since every language can be converted into binary-string form, below we take $\Sigma=\{0, 1\}$ unless stated otherwise.

Decision Problems

A decision problem is a problem whose answer can only be YES or NO. Essentially, it asks whether a string belongs to a language: $f:\Sigma^\ast\rightarrow\{0, 1\}, f(x)=1\iff x\in L$ defines a decision problem over alphabet $\Sigma$ and language $L$. For example, “deciding whether a graph is a directed acyclic graph” is a decision problem.

Decision problems are often studied in computability theory because of their simplicity. Unless stated otherwise, “problem” in this article means “decision problem”; some statements can of course be extended to other kinds of problems.

A language may also refer to the decision problem of determining whether a string belongs to it. Thus, “language” and “problem” can be treated as synonyms.

Functional Problems

A functional problem can have answers other than YES or NO, such as a number. For example, “find the sum of two numbers” is a functional problem.

Every functional problem can be converted into a decision problem. For example, “find the sum of two numbers” can become “decide whether the sum of two numbers equals a third number”.

A decision problem can also be converted into a functional problem: compute its indicator function, namely the $f$ in the definition above.

Turing Machines

Deterministic Turing Machines

Unless stated otherwise, “Turing machine” usually means “deterministic Turing machine”, and that is the convention here.

There are many definitions of a Turing machine. We use one of them here; Turing machines under other definitions generally have equivalent computational power.

A Turing machine is a machine operating on a tape that extends infinitely in both directions and is divided into cells. It has internal states and a head that can modify the tape and move along it.

Formally, a Turing machine is a 7-tuple $M=\langle Q,\Gamma,b,\Sigma,\delta,q_0,F\rangle$, where:

• $Q$ is a finite nonempty set of states;
• $\Gamma$ is a finite nonempty tape alphabet;
• $b\in\Gamma$ is the blank symbol, the only symbol that may appear on the tape infinitely often during computation;
• $\Sigma\subseteq(\Gamma\setminus\{b\})$ is the input alphabet, whose symbols may appear on the initial tape (the input);
• $q_0\in Q$ is the initial state;
• $F\subseteq Q$ is the set of accepting states. If a Turing machine halts in an accepting state, the contents of its initial tape are said to be accepted by the machine.
• $\delta :(Q\setminus F)\times \Gamma \not \to Q\times \Gamma \times \{L,R\}$ is a partial function called the transition function (a function defined only on a subset of its domain). If $\delta$ is undefined for the current state, the Turing machine halts.

Starting from the initial state and the beginning of the tape, the Turing machine acts at each step according to its current internal state $x$ and the symbol $y$ in the cell currently under the head: if $\delta(x, y)$ is undefined, it halts; otherwise, if $\delta(x, y)=(a, b, c)$, it changes the internal state to $a$, changes the symbol in the cell to $b$, and moves one cell left if $c$ is $L$ or one cell right if $R$ is $R.

In fact, knowing the operational details of a Turing machine is unnecessary; an intuitive understanding is enough.

The output of Turing machine $M$ on input $x$ is denoted by $M(x)$ ($M(x)=1$ if and only if $M$ accepts $x$; $M(x)=0$ if and only if $M$ halts after finitely many steps on input $x$ without $M$ accepting $x$). Multiple parameters may also be placed in the parentheses and separated by commas; in an implementation, a symbol representing a comma can be added to the alphabet.

The time complexities of Turing machines and von Neumann computers for solving problems differ only polynomially, so Turing machines can be used as a computational model when studying complexity classes.

Nondeterministic Turing Machines

A nondeterministic Turing machine is a type of Turing machine. Unlike a deterministic Turing machine, which can transition to only one state at each step, it can “simultaneously” transition to multiple states and compute along multiple “branches” in parallel. If any branch halts in an accepting state, the nondeterministic Turing machine accepts the input.

In fact, any deterministic Turing machine can simulate the polynomial-time behavior of a nondeterministic Turing machine in exponential time using a method similar to iterative deepening search.

In real life, a deterministic Turing machine is analogous to a single-core processor supporting only serial processing, while a nondeterministic Turing machine is analogous to an ideal multicore processor supporting parallel processing of unlimited size.

Multitape Turing Machines

A standard Turing machine operates on only one tape, but for convenience this article studies multitape Turing machines. For a $k$-tape machine, one tape is a read-only input tape, while the remaining $k-1$ tapes are readable and writable, and one of these $k-1$ tapes is used as the output tape.

A multitape Turing machine must have finitely many tapes.

For a multitape Turing machine, its space usage is the number of cells visited by the heads on tapes other than the input tape.

Encoding Turing Machines

Turing machines can be encoded by natural numbers: there is a surjective function $f:\mathbb{N}\to\mathbb{M}$ such that every natural number corresponds to a Turing machine, while every Turing machine has infinitely many encodings. Therefore, a set consisting of Turing machines can be a language.

Let $\alpha$ denote the Turing machine encoded by the natural number $M_{\alpha}$.

Universal Turing Machine

There exists a Turing machine $\mathcal U$ such that:

1. If $M_{\alpha}$ halts in finite time on input $x$, then $\mathcal{U}(x, \alpha)=M_{\alpha}(x)$; otherwise, $\mathcal{U}(x, \alpha)$ does not halt in finite time;
2. If, for every $x\in\{0, 1\}^\ast$, $M_\alpha$ halts in $x$ time on input $T(|x|)$, then, for every $x\in\{0, 1\}^\ast$, $\mathcal{U}(x, \alpha)$ halts in $O(T(|x|)\log T(|x|))$ time.

In other words, there is a universal Turing machine that can simulate any Turing machine, with only a logarithmic slowdown relative to the simulated machine's running time.

Computability

Uncomputable Problems

For a decision problem, if there is a Turing machine that always halts in finitely many steps and decides it correctly, the problem is Turing-computable; otherwise, it is Turing-uncomputable.

Because Turing machines can be encoded by natural numbers, there are countably infinitely many Turing machines, whereas there are uncountably many languages (sets of binary strings). Since each Turing machine decides at most one language, uncomputable problems must exist.

Halting Problem

The halting problem is a classic Turing-uncomputable problem: given $\alpha$ and $x$, decide whether $M_{\alpha}$ halts in finitely many steps on input $x$.

Proof that the Halting Problem Is Turing-Uncomputable

Define $\mathsf{UC}:\{0,1\}^\ast\to\{0,1\}$ by:

$$\mathsf{UC}(\alpha)=\begin{cases}0&M_\alpha(\alpha)=1\\1&\text{otherwise}\end{cases}$$

We first prove that $\mathsf{UC}$ is Turing-uncomputable:

Suppose a Turing machine $M_{\beta}$ computes $\mathsf{UC}$. By the definition of $\mathsf{UC}$, we get $\mathsf{UC}(\beta)=1\iff M_\beta(\beta)\neq 1$, while by the assumption that $M_{\beta}$ computes $\mathsf{UC}$, we get $M_{\beta}(\beta)=\mathsf{UC}(\beta)$, a contradiction. Thus the assumption is false, and no Turing machine computes $\mathsf{UC}$.

Let $M_{\mathsf{HALT}}$ be a Turing machine that solves the halting problem, so that $M_{\mathsf{HALT}}(x,\alpha)$ decides whether $M_\alpha$ halts in finitely many steps on input $x$. We can then construct a Turing machine $\mathsf{UC}$ that computes $M_{\mathsf{UC}}$:

$M_\mathsf{UC}$ first calls $M_\mathsf{HALT}(α,α)$. If it outputs $0$, then $M_\mathsf{UC}(α)=1$; otherwise, $M_\mathsf{UC}$ uses a universal Turing machine to simulate the computation and obtain the answer.

Since $\mathsf{UC}$ is Turing-uncomputable, $M_\mathsf{HALT}$ does not exist; in other words, the halting problem is Turing-uncomputable.

Church–Turing Thesis

The Church–Turing thesis states that if a class of problems has an effective method of solution, then the class can be solved by some Turing machine.

Here, an “effective method” must satisfy:

1. contain finitely many clear instructions;
2. when used to solve one problem in the class, terminate in finitely many steps and produce the correct answer.

This thesis has not been proved, but it is a basic axiom of computability theory.

Complexity Classes

There are many complexity classes; this article introduces only a small selection of the more common ones.

R and RE

For a language $L$ and Turing machine $M$, if $M$ halts in finitely many steps on every input and $M(x)=1\iff x\in L$, then $M$ is said to decide $L$.

For a language $L$ and Turing machine $M$, if $L$ halts in finitely many steps for every input in $M$ and $M(x)=1\iff x\in L$, then $M$ is said to recognize $L$.

The complexity class $\mathsf R$ is the set of languages decidable by some Turing machine, namely all Turing-computable languages.

The complexity class $\mathsf{RE}$ is the set of languages recognizable by some Turing machine. $\mathsf{RE}$ is also called the class of recursively enumerable languages.

By definition, $\mathsf{R}\subseteq\mathsf{RE}$.

DTIME

If a deterministic Turing machine decides a language and halts in $x$ time for every input $O(f(|x|))$, then the language belongs to $\mathsf{DTIME}(f(n))$.

P

The complexity class $\mathsf P$ consists of decision problems solvable by a deterministic Turing machine in polynomial time, namely:

$$\mathsf{P}=\bigcup\limits_{k\in\mathbb{N}}\mathsf{DTIME}(n^k)$$

Linear programming, computing the greatest common divisor, and the decision version of finding a maximum matching in a graph are all problems in $\mathsf P$.

EXPTIME

The complexity class $\mathsf{EXPTIME}$ consists of decision problems solvable by a deterministic Turing machine in exponential time, namely:

$$\mathsf{EXPTIME}=\bigcup\limits_{k\in\mathbb{N}}\mathsf{DTIME}(2^{n^k})$$

A weakened version of the halting problem—given an encoding of a Turing machine and a positive integer $k$, decide whether the machine halts within $k$ steps—is in $\mathsf{EXPTIME}$. Its solution takes $O(k)$ time, while $k$ can be encoded as a binary string of length $O(\log k)$.

NTIME

If a nondeterministic Turing machine decides a language and halts in $x$ time for every input $O(f(|x|))$, then the language belongs to $\mathsf{NTIME}(f(n))$.

NP

The complexity class $\mathsf{NP}$ consists of decision problems solvable by a nondeterministic Turing machine in polynomial time, namely:

$$\mathsf{NP}=\bigcup\limits_{k\in\mathbb{N}}\mathsf{NTIME}(n^k)$$

Every problem in $\mathsf P$ is in $\mathsf{NP}$. For more problems in $\mathsf{NP}$, see the NPC and NP-intermediate problems below.

NP-hard

If every problem in $\mathsf{NP}$ can be reduced to problem $H$ in polynomial time, then $H$ is NP-hard.

In other words, if NP-hard problem $H$ could be solved in one unit of time, then every problem in $\mathsf{NP}$ could be solved in polynomial time.

NP-complete

If a problem is both in $\mathsf{NP}$ and NP-hard, it is NP-complete, or an NPC problem.

Classic NPC problems include the decision versions of the traveling salesperson, maximum independent set, minimum vertex cover, longest path, and 0–1 integer programming problems, as well as set cover, graph coloring, knapsack, three-dimensional matching, and the decision version of maximum cut.

The functional version of an NPC problem is often NP-hard. For example, “decide whether a graph contains a clique of size $k$” is both in $\mathsf{NP}$ and NP-hard, so it is an NPC problem; its functional version, “find the maximum clique of a graph”, is not an NPC problem but is still NP-hard.

Similarly, other complexity classes have “XX-complete” problems; for example, every problem in $\mathsf{EXPTIME}$ can be reduced in polynomial time to an EXPTIME-complete problem.

co-NP

A problem is in $\mathsf{co-NP}$ if and only if its complement is in $\mathsf{NP}$. If “problem” is understood as “language”, and a language is a subset of $\Sigma^\ast$, the meaning of “complement” is clear.

For example, “given $n$ subsets, decide whether $k$ of them can cover the entire set” is an NPC problem, while its complement, “given $n$ subsets, decide whether no choice of $k$ subsets can cover the entire set”, is in $\mathsf{co-NP}$. If the answer to the first problem is YES, we have found a counterexample to the second, whose answer is therefore NO.

NP-intermediate

A problem in $\mathsf{NP}$ that is neither in $\mathsf{P}$ nor NPC is called an NP-intermediate problem.

As far as currently known, graph isomorphism, discrete logarithm, and integer factorization may be NP-intermediate.

Ladner's theorem states that if $\mathsf{P}\ne\mathsf{NP}$, then an NP-intermediate problem must exist.

NEXPTIME

The complexity class $\mathsf{NEXPTIME}$ consists of decision problems solvable by a nondeterministic Turing machine in exponential time, namely:

$$\mathsf{NEXPTIME}=\bigcup\limits_{k\in\mathbb{N}}\mathsf{NTIME}(2^{n^k})$$

#P

Problems in $\mathsf{\#P}$ are not decision problems, but counting problems about $\mathsf{NP}$ problems: counting the number of solutions to an $\mathsf{NP}$ problem is a $\mathsf{\#P}$ problem. Equivalently, counting the number of branches of a nondeterministic Turing machine that always halts in polynomial time on which a string is accepted is a $\mathsf{\#P}$ problem.

Counting matchings or perfect matchings in an ordinary graph or a bipartite graph is #P-complete; the corresponding decision problem is “decide whether a graph has a (perfect) matching”.

DSPACE

If a deterministic Turing machine can decide a language using $x$ space on input $O(f(|x|))$, then the language belongs to $\mathsf{DSPACE}(f(n))$.

• $\mathsf{REG}=\mathsf{DSPACE}(O(1))$，that is, the regular languages, namely the languages decidable by automata.

• $\mathsf{L}=\mathsf{DSPACE}(O(\log n))$，Note that the space used by a Turing machine does not include the space occupied by the input.

• $\mathsf{PSPACE}=\bigcup\limits_{k\in\mathbb N}\mathsf{DSPACE}(n^k)$

• $\mathsf{EXPSPACE}=\bigcup\limits_{k\in\mathbb N}\mathsf{DSPACE}(2^{n^k})$

NSPACE

If a nondeterministic Turing machine can decide a language using $x$ space on input $O(f(|x|))$, then the language belongs to $\mathsf{NSPACE}(f(n))$.

• $\mathsf{REG}=\mathsf{DSPACE}(O(1))=\mathsf{NSPACE}(O(1))$

• $\mathsf{NL}=\mathsf{NSPACE}(O(\log n))$

• $\mathsf{CSL}=\mathsf{NSPACE}(O(n))$，that is, the context-sensitive languages.

• $\mathsf{PSPACE}=\mathsf{NPSPACE}=\bigcup\limits_{k\in\mathbb N}\mathsf{NSPACE}(n^k)$

• $\mathsf{EXPSPACE}=\mathsf{NEXPSPACE}=\bigcup\limits_{k\in\mathbb N}\mathsf{NSPACE}(2^{n^k})$

Polynomial Time

Simply put, if there is a positive number $k$ such that an algorithm has time complexity $O(n^k)$ (not $\Theta(n^k)$), where $n$ is the problem size (the input length), then the algorithm runs in polynomial time. If a problem has a polynomial-time algorithm on a deterministic Turing machine, it belongs to $\mathsf{P}$.

Polynomial time can be divided into strongly and weakly polynomial time; there is also pseudo-polynomial time.

Strongly Polynomial Time

First define a computational model called the arithmetic model. In it, arithmetic operations on numbers (addition, subtraction, multiplication, division, and comparison) take unit time (that is, $O(1)$ time regardless of the numbers' sizes).

If an algorithm uses a polynomial number of operations in the number of input numbers in the arithmetic model, and its space complexity is polynomial in the input size (rather than the number of numbers), then it runs in strongly polynomial time. Since arithmetic operations can be performed in polynomial time in the input size (the logarithm of the numbers' sizes) in the usual model, every strongly polynomial-time algorithm is polynomial-time.

In general, the time complexity of a strongly polynomial-time algorithm is independent of the value range.

Weakly Polynomial Time

If an algorithm is polynomial-time but not strongly polynomial-time, it is weakly polynomial-time.

For example, Euclid's algorithm for computing the greatest common divisor has time complexity $O(\log a + \log b)$, where $a$ and $b$ are the input numbers, and is weakly polynomial-time.

Pseudo-Polynomial Time

If an algorithm's running time is polynomial in the value range, it is pseudo-polynomial-time. A pseudo-polynomial-time algorithm may or may not be polynomial-time. It may fail to be polynomial-time because a positive integer of size $n$ generally needs only $O(\log n)$ bits, so a value-polynomial algorithm is often exponential in the input length. Although it can technically be polynomial-time, calling an algorithm pseudo-polynomial-time generally means that it is not polynomial-time.

For example, knapsack is NP-hard but has a dynamic-programming pseudo-polynomial-time solution.

If an NPC/NP-hard problem has a pseudo-polynomial-time solution, it is called a weakly NPC/weakly NP-hard problem. If an NPC/NP-hard problem has no pseudo-polynomial-time solution assuming $\mathsf{P} \ne \mathsf{NP}$, it is called a strongly NPC/strongly NP-hard problem.

Constructible Functions

Time-Constructible Functions

Sometimes we want a Turing machine to know how much time it has used, for example to force it to halt after $T(n)$ steps. This is impossible if computing $T(n)$ itself takes longer than $T(n)$. Time-constructible functions are defined to avoid this issue.

If there is a Turing machine $M$ that, on input $1^n$ ($n$ ones), $M$ halts in $O(f(n))$ time and outputs the binary representation of $f(n)$ (the output here is a string, not acceptance or rejection, and can be written on the tape), then $f(n)$ is time-constructible.

Since reading the input takes $O(n)$ time, no nonconstant function in $o(n)$ is time-constructible.

Space-Constructible Functions

Space-constructible functions can be defined similarly.

If there is a Turing machine $M$ that, on input $1^n$ ($n$ ones), $M$ halts using $O(f(n))$ space and outputs the binary representation of $f(n)$, then $f(n)$ is space-constructible.

Relations Between Complexity Classes

Time Hierarchy Theorems

Deterministic Time Hierarchy Theorem

If $f(n)$ is time-constructible, then:

$$\mathsf {DTIME}\left(o\left({\frac {f(n)}{\log f(n)}}\right)\right)\subsetneq \mathsf {DTIME}(f(n))$$

The deterministic time hierarchy theorem gives $\mathsf{P}\subsetneq\mathsf{EXPTIME}$.

Proof of the Deterministic Time Hierarchy Theorem

Define the language $L=\{(x, y)|\mathcal{U}((x, y), x)\text{ 在 }f(|x|+|y|)\text{ 时间内停机并拒绝}\}$. Since $f(n)$ is time-constructible, $L$ can be decided from this definition in $O(f(|x|+|y|))$ time, so $L\in\mathsf{DTIME}(f(n))$.

Now suppose $L\in\mathsf{DTIME}(o\left({\dfrac {f(n)}{\log f(n)}}\right))$, and let $M_z$ be the Turing machine that decides $o\left({\dfrac {f(n)}{\log f(n)}}\right)$ in $L$ time.

Let the running time of the universal Turing machine $\mathcal{U}(x, z)$ as a function of $x$ be $g(|x|)$. From the discussion of universal Turing machines above, $g(n)=o(f(n))$, so for sufficiently large $y$, $g(|z|+|y|)<f(|z|+|y|)$.

Let $y'$ be a sufficiently large $y$. Then $\mathcal{U}((z, y'), z)$ must halt within $f(|z|+|y'|)$ time, giving $M_z(z, y')\ne M_z(z, y')$, a contradiction. Thus the assumption is false, proving the deterministic time hierarchy theorem.

Nondeterministic Time Hierarchy Theorem

If $g(n)$ is time-constructible and $f(n+1)=o(g(n))$, then $\mathsf{NTIME}(f(n))\subsetneq\mathsf{NTIME}(g(n))$.

The nondeterministic time hierarchy theorem gives $\mathsf{NP}\subsetneq\mathsf{NEXPTIME}$.

Space Hierarchy Theorem

If $f(n)$ is space-constructible and $f(n)=\Omega(\log n)$, then $\mathsf{SPACE}(o(f(n)))\subsetneq\mathsf{SPACE}(f(n))$.

Here $\mathsf{SPACE}$ may denote either $\mathsf{DSPACE}$ or $\mathsf{NSPACE}$.

The space hierarchy theorem gives $\mathsf{PSPACE}\subsetneq\mathsf{EXPSPACE}$.

Savitch's Theorem

A deterministic Turing machine can simulate a nondeterministic Turing machine using the square of its space consumption (although it may use much more time), namely:

If $f(n)=\Omega(\log n)$, then:

$$\mathsf{NSPACE}\left(f\left(n\right)\right)\subseteq \mathsf {DSPACE}\left(\left(f\left(n\right)\right)^2\right)$$

Corollary: $\mathsf{PSPACE}=\mathsf{NPSPACE}$ and $\mathsf{EXPSPACE}=\mathsf{NEXPSPACE}$.

P?=NP

Whether the complexity classes $\mathsf{P}$ and $\mathsf{NP}$ are equal is a famous open problem in computational complexity theory.

If $\mathsf{P}=\mathsf{NP}$, then $\mathsf{NP}=\mathsf{co-NP}$, but the converse does not follow (there is currently no way to prove $\mathsf{NP}=\mathsf{co-NP}$ from $\mathsf{P}=\mathsf{NP}$).

Why Isn't NP?=co-NP Obvious?

Because an $\mathsf{NP}$ problem and its corresponding $\mathsf{co-NP}$ problem have opposite answers, it is tempting to think that, for a $\mathsf{co-NP}$ problem, we can simply reverse the output of the nondeterministic Turing machine that solves its $\mathsf{co-NP}$ complement, and thus obtain $\mathsf{NP}=\mathsf{co-NP}$.

In fact, this method does solve the $\mathsf{co-NP}$ problem, but it does not produce a nondeterministic Turing machine that solves it. If a machine reverses the output of a nondeterministic Turing machine, it is not itself a nondeterministic Turing machine: a nondeterministic Turing machine accepts when some branch accepts and rejects when all branches reject. Reversing the output would make it accept when all branches accept and reject when one branch rejects, which does not match the definition of a nondeterministic Turing machine. Thus, solving this $\mathsf{co-NP}$ problem with that machine for this $\mathsf{co-NP}$ problem does not make the problem an $\mathsf{NP}$ problem.

If $\mathsf{P}=\mathsf{NP}$, then $\mathsf{EXPTIME}=\mathsf{NEXPTIME}$.

If $\mathsf{P}\ne\mathsf{NP}$, then NP-intermediate is nonempty.

References

1. Computational Complexity (1): Automata and Regular Languages；

2. Computational Complexity (2): Turing Machines and Computability；

3. Wikipedia relevant entries and their references.