Computational Theory Basics

This section introduces basic knowledge of computational theory. This content is not very useful in OI (but still somewhat useful: if you encounter an NP-hard problem, you can assume it does not have a polynomial-time solution). It can be understood as an interest or as preparation for future studies.

Many conclusions in this article are presented without proof. If interested, you can look up the relevant proofs yourself.

Prerequisite: Time Complexity.

Problems

Language

An alphabet is a non-empty finite set, and the elements of this set are called symbols/characters.

Let \(\Sigma^\ast\) denote strings formed by concatenating zero or more characters from \(\Sigma\). A language over alphabet \(\Sigma\) is a subset of \(\Sigma^\ast\).

Note that "language" here is an abstract concept. Ordinary strings are languages, and all directed acyclic graphs can also be a language (there exists a bijection between 01 strings and directed graphs; the specific method is not necessary to understand).

Since any language can be transformed into a form of 01 strings, in the following, unless otherwise specified, \(\Sigma=\{0, 1\}\).

Decision Problems

A decision problem is one that can only be answered with YES/NO. Essentially, it decides whether a string belongs to a language, i.e., \(f:\Sigma^\ast\rightarrow\{0, 1\}, f(x)=1\iff x\in L\) is a decision problem about alphabet \(\Sigma\) and language \(L\). For example, "determine whether a graph is a directed acyclic graph" is a decision problem.

Due to their simplicity, decision problems are often the object of study in computational theory. In this article, unless otherwise specified, "problem" refers to "decision problem," although some propositions can be simply extended to other problems.

A language can also refer to the decision problem "determine whether a string belongs to this language." Therefore, "language" and "problem" can be considered synonyms.

Functional Problems

Functional problems have answers beyond YES/NO; they can be a number or something else. For example, "find the sum of two numbers" is a functional problem.

Any functional problem can be transformed into a decision problem. For example, "find the sum of two numbers" can be transformed into "determine whether the sum of two numbers equals a third number."

A decision problem can also be transformed into a functional problem: compute the indicator function of the decision problem, i.e., \(f\) in the definition of decision problem above.

Turing Machines

Deterministic Turing Machine

Unless otherwise specified, "Turing machine" often refers to "deterministic Turing machine," and this article follows this convention.

There are many different definitions of Turing machines. Here we choose one; Turing machines under other definitions are often computationally equivalent to those defined below.

A Turing machine is a machine that operates on an infinitely extendable tape divided into cells. It has internal states and a read-write head that can modify and move along the tape.

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

\(Q\) is a finite non-empty set of states;
\(\Gamma\) is a finite non-empty tape alphabet;
\(b\in\Gamma\) is the blank symbol, the only symbol that can appear infinitely often on the tape during computation;
\(\Sigma\subseteq(\Gamma\setminus\{b\})\) is the input symbol set, characters that can appear on the initial tape (i.e., 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 initial tape content is said to be accepted by this Turing machine.
\(\delta :(Q\setminus F)\times \Gamma \not \to Q\times \Gamma \times \{L,R\}\) is a partial function called the transition function (i.e., a function defined only on a subset of its domain). If \(\delta\) is undefined at the current state, the Turing machine halts.

The Turing machine starts from the initial state and the tape's starting position. At each step, based on the current internal state \(x\) and the character \(y\) in the cell pointed to by the head, it operates: 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 character in the cell pointed to by the head to \(b\), and moves one cell left if \(c\) is \(L\), or right if \(c\) is \(R\).

Actually, knowing the details of how a Turing machine works is unnecessary; an intuitive understanding is sufficient.

The output of Turing machine \(M\) on input \(x\) is denoted \(M(x)\) (\(M(x)=1\) if and only if \(M\) accepts \(x\); \(M(x)=0\) if and only if \(M\) halts within a finite number of steps on input \(x\) and \(M\) does not accept \(x\)). Multiple parameters can also be included in parentheses, separated by commas. In implementation, an element representing a comma can be added to the alphabet to separate parameters.

The difference in time complexity between Turing machines and von Neumann computers is within a polynomial factor, so Turing machines can be used as a computational model when studying complexity classes.

Nondeterministic Turing Machine

A nondeterministic Turing machine is a type of Turing machine. The difference from a deterministic Turing machine is: a deterministic Turing machine can only transition to one state at each step, while a nondeterministic Turing machine can "simultaneously" transition to multiple states, thus performing parallel computation in multiple "branches." Once one of these "branches" halts in an accepting state, this nondeterministic Turing machine accepts the input.

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

In real life, a deterministic Turing machine is like a single-core processor, supporting only serial processing; a nondeterministic Turing machine is like an ideal multi-core processor, supporting unlimited parallel processing.

Multi-tape Turing Machine

A standard Turing machine can only operate on one tape, but for convenience, this article studies multi-tape Turing machines. For a \(k\)-tape Turing machine, one tape is a read-only input tape, while the remaining \(k-1\) tapes are read-write, and among these \(k-1\) tapes, one is used for output.

The number of tapes in a multi-tape Turing machine must be finite.

For a multi-tape Turing machine, the space it uses is the number of cells visited by the heads on tapes other than the input tape.

Encoding of Turing Machines

Turing machines can be encoded by natural numbers, i.e., there exists a surjective function \(f:\mathbb{N}\to\mathbb{M}\) such that each natural number corresponds to a Turing machine, and each Turing machine has infinitely many encodings. Therefore, a set consisting of several Turing machines can be a language.

Denote the Turing machine encoded by natural number \(\alpha\) as \(M_{\alpha}\).

Universal Turing Machine

There exists a Turing machine \(\mathcal U\) such that:

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

That is: there exists a universal Turing machine that can simulate any Turing machine, and the time spent is only slower by a logarithmic factor of the running time of the simulated Turing machine.

Computability

Uncomputable Problems

For a decision problem, if there exists a Turing machine that always halts within a finite number of steps and correctly decides the problem, then this problem is Turing computable; otherwise, it is Turing uncomputable.

Since Turing machines can be encoded by natural numbers, the number of Turing machines is countably infinite, while the number of languages (i.e., sets of binary strings) is uncountably infinite. Each Turing machine can decide at most one language, so there must exist Turing uncomputable problems.

Halting Problem

The halting problem is a classic Turing uncomputable problem: given \(\alpha\) and \(x\), determine whether \(M_{\alpha}\) halts within a finite number of steps on input \(x\).

Proof that the Halting Problem is Turing Uncomputable

Define function \(\mathsf{UC}:\{0,1\}^\ast\to\{0,1\}\) as:

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

We first prove that the \(\mathsf{UC}\) function is Turing uncomputable:

Assume there exists a Turing machine \(M_{\beta}\) that can compute \(\mathsf{UC}\). Then, according to the definition of \(\mathsf{UC}\), we have \(\mathsf{UC}(\beta)=1\iff M_\beta(\beta)\neq 1\), and since \(M_{\beta}\) can compute \(\mathsf{UC}\), we have \(M_{\beta}(\beta)=\mathsf{UC}(\beta)\), leading to a contradiction. Therefore, the assumption is false; there is no Turing machine that can compute \(\mathsf{UC}\).

Let \(M_{\mathsf{HALT}}\) be a Turing machine that can solve the halting problem. \(M_{\mathsf{HALT}}(x,\alpha)\) is the answer to the decision problem: whether \(M_\alpha\) halts within a finite number of steps on input \(x\). Then we can construct a Turing machine \(M_{\mathsf{UC}}\) that can compute the \(\mathsf{UC}\) function:

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

Since the \(\mathsf{UC}\) function is Turing uncomputable, \(M_\mathsf{HALT}\) does not exist, meaning 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 this class of problems can be solved by some Turing machine.

Here, "effective method" must satisfy:

It consists of a finite number of clear instructions.
When used to solve one of these problems, the method must terminate in a finite number of steps and produce the correct answer.

This thesis is not proven but is a fundamental axiom of computational theory.

Complexity Classes

There are many complexity classes; this article will only introduce a small subset of the more common ones.

R and RE

For a language \(L\) and a Turing machine \(M\), if \(M\) halts within a finite number of steps on any input, and \(M(x)=1\iff x\in L\), then \(M\) decides \(L\).

For a language \(L\) and a Turing machine \(M\), if for any input belonging to \(L\), \(M\) halts within a finite number of steps, and \(M(x)=1\iff x\in L\), then \(M\) recognizes \(L\).

The complexity class \(\mathsf R\) denotes the set of languages that can be decided by some Turing machine, i.e., all Turing computable languages.

The complexity class \(\mathsf{RE}\) denotes the set of languages that can be recognized by some Turing machine. \(\mathsf{RE}\) is also called recursively enumerable languages.

From the definitions, we have \(\mathsf{R}\subseteq\mathsf{RE}\).

DTIME

If there exists a deterministic Turing machine that can decide a language, and for any input \(x\), this Turing machine can halt within \(O(f(|x|))\) time, then this language belongs to the class \(\mathsf{DTIME}(f(n))\).

P

The complexity class \(\mathsf P\) denotes decision problems that can be solved by a deterministic Turing machine in polynomial time, i.e.:

\[ \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 \(\mathsf P\) class problems.

EXPTIME

The complexity class \(\mathsf{EXPTIME}\) denotes decision problems that can be solved by a deterministic Turing machine in exponential time, i.e.:

\[ \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\), determine whether this Turing machine halts within \(k\) steps—is an \(\mathsf{EXPTIME}\) class problem. Because solving this problem requires \(O(k)\) time, and the number \(k\) can be encoded as a binary string of length \(O(\log k)\).

NTIME

If there exists a nondeterministic Turing machine that can decide a language, and for any input \(x\), this Turing machine can halt within \(O(f(|x|))\) time, then this language belongs to the class \(\mathsf{NTIME}(f(n))\).

NP

The complexity class \(\mathsf{NP}\) denotes decision problems that can be solved by a nondeterministic Turing machine in polynomial time, i.e.:

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

All \(\mathsf P\) class problems are \(\mathsf{NP}\) class problems. For more \(\mathsf{NP}\) class problems, see the NPC problems and NP-intermediate problems below.

NP-hard

If all \(\mathsf{NP}\) class problems can be reduced to problem \(H\) in polynomial time, then problem \(H\) is NP-hard.

In other words, if an NP-hard problem \(H\) can be solved in one unit of time, then all \(\mathsf{NP}\) class problems can be solved in polynomial units of time.

NP-complete

If a problem is both an \(\mathsf{NP}\) class problem and NP-hard, then the problem is NP-complete, or it is an NPC problem.

Some classic NPC problems: the decision version of the traveling salesman problem, the decision version of the maximum independent set problem, the decision version of the minimum vertex cover problem, the decision version of the longest path problem, the decision version of the 0-1 integer programming problem, the set cover problem, graph coloring, the knapsack problem, 3-dimensional matching, the decision version of the maximum cut problem.

The functional versions of NPC problems are often NP-hard. For example: "determine whether a graph contains a clique of size \(k\)" is both an \(\mathsf{NP}\) class problem and NP-hard, making it an NPC problem. Its functional version "find the maximum clique in a graph" is not an NPC problem, but this functional version is still NP-hard.

Similarly, other complexity classes also have "XX-complete," e.g., all \(\mathsf{EXPTIME}\) class problems can be reduced to EXPTIME-complete problems in polynomial time.

co-NP

A problem is a \(\mathsf{co-NP}\) class problem if and only if its complement is an \(\mathsf{NP}\) class problem. If "problem" is understood as "language," and "language" is a subset of \(\Sigma^\ast\), then "complement" can be understood.

For example: "Given \(n\) subsets, determine whether \(k\) of them can be selected to cover the entire set" is an NPC problem. Its complement "Given \(n\) subsets, determine whether any \(k\) of them cannot cover the entire set" is a \(\mathsf{co-NP}\) class problem. If the answer to the first problem is "yes," it is equivalent to finding a counterexample for the second problem, so the answer to the second problem is "no."

NP-intermediate

If a problem is an \(\mathsf{NP}\) class problem but is neither a \(\mathsf{P}\) class problem nor an NPC problem, it is called an NP-intermediate problem.

Based on current knowledge, the graph isomorphism problem, the discrete logarithm problem, and the integer factorization problem may be NP-intermediate.

Ladner's theorem states that if \(\mathsf{P}\ne\mathsf{NP}\), then there must exist NP-intermediate problems.

NEXPTIME

The complexity class \(\mathsf{NEXPTIME}\) denotes decision problems that can be solved by a nondeterministic Turing machine in exponential time, i.e.:

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

#P

\(\mathsf{\#P}\) class problems are not decision problems but counting problems about \(\mathsf{NP}\) class problems: counting the number of solutions to an \(\mathsf{NP}\) class problem is a \(\mathsf{\#P}\) class problem. In other words, counting how many branches of a nondeterministic Turing machine that always halts in polynomial time accept a given string is a \(\mathsf{\#P}\) class problem.

Counting the number of matchings or perfect matchings in an ordinary graph or bipartite graph is #P-complete. The corresponding decision problem is "determine whether a graph has a (perfect) matching."

DSPACE

If there exists a deterministic Turing machine that can decide a language within \(O(f(|x|))\) space when the input is \(x\), then this language belongs to the class \(\mathsf{DSPACE}(f(n))\).

\(\mathsf{REG}=\mathsf{DSPACE}(O(1))\), i.e., regular languages, which are languages that can be decided by automata.
\(\mathsf{L}=\mathsf{DSPACE}(O(\log n))\). Note that the space used by the 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 there exists a nondeterministic Turing machine that can decide a language within \(O(f(|x|))\) space when the input is \(x\), then this language belongs to the class \(\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))\), i.e., 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 exists a positive number \(k\) such that an algorithm's time complexity is \(O(n^k)\) (note, not \(\Theta(n^k)\)), where \(n\) is the problem size (length of input), then the algorithm is polynomial time. If a problem has a polynomial-time algorithm (on a deterministic Turing machine) to solve it, then the problem belongs to the complexity class \(\mathsf{P}\).

Polynomial time can be divided into strongly polynomial time and weakly polynomial time, in addition to pseudo-polynomial time.

Strongly polynomial time

We first define a computational model called the arithmetic model. In the arithmetic model, arithmetic operations between numbers (addition, subtraction, multiplication, division, comparison) can be completed in unit time (i.e., \(O(1)\) time, independent of the size of the numbers).

If an algorithm's number of operations in the arithmetic model is a polynomial in the number of numbers in the input, and its space complexity is a polynomial in the input size (not the number of numbers), then the algorithm is strongly polynomial time. Since arithmetic operations in general computational models can be completed in time polynomial in the input size (i.e., the logarithm of the number sizes), strongly polynomial-time algorithms are always polynomial-time.

Generally, the time complexity of strongly polynomial-time algorithms is independent of the value range.

Weakly polynomial time

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

For example, the Euclidean algorithm for computing the greatest common divisor has time complexity \(O(\log a + \log b)\) (where \(a\) and \(b\) are the sizes of 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 said to be pseudo-polynomial time. A pseudo-polynomial-time algorithm may or may not be polynomial-time; it may not be polynomial-time because representing a positive integer of size \(n\) generally requires only \(O(\log n)\) bits, so algorithms with running time polynomial in the value range are often exponential in the input length. Although by definition pseudo-polynomial time could also be polynomial time, when we say an algorithm is pseudo-polynomial time, we usually mean it is not polynomial-time.

For example, the knapsack problem is NP-hard, but it has a pseudo-polynomial-time solution based on dynamic programming.

If an NPC/NP-hard problem has a pseudo-polynomial-time solution, the problem is called weak NPC/weak NP-hard. If an NPC/NP-hard problem has no pseudo-polynomial-time solution under the assumption \(\mathsf{P} \ne \mathsf{NP}\), then the problem is called strong NPC/strong NP-hard.

Constructible Functions

Time-constructible functions

Sometimes we want a Turing machine to know how much time it has used, e.g., force the Turing machine to halt after exactly \(T(n)\) steps of computation. But if computing \(T(n)\) itself takes more than \(T(n)\) time, this is impossible. To avoid such trouble, time-constructible functions are defined.

If there exists a Turing machine \(M\) such that on input \(1^n\) (\(n\) ones) \(M\) halts within \(O(f(n))\) time and outputs the binary representation of \(f(n)\) (note: here the Turing machine's output is not accept/reject but a string; output can be on the tape), then \(f(n)\) is a time-constructible function.

Since reading input takes \(O(n)\) time, non-constant functions in \(o(n)\) are not time-constructible.

Space-constructible functions

Similarly, space-constructible functions can be defined.

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

Relationships Between Complexity Classes

Time Hierarchy Theorems

Deterministic Time Hierarchy Theorem

If \(f(n)\) is a time-constructible function, then:

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

From the deterministic time hierarchy theorem, we get \(\mathsf{P}\subsetneq\mathsf{EXPTIME}\).

Proof of the Deterministic Time Hierarchy Theorem

Define language \(L=\{(x, y)|\mathcal{U}((x, y), x)\text{ halts and rejects within }f(|x|+|y|)\text{ time}\}\). Since \(f(n)\) is time-constructible, \(L\) can be decided by computing according to the definition, taking \(O(f(|x|+|y|))\) time, so \(L\in\mathsf{DTIME}(f(n))\).

Now assume \(L\in\mathsf{DTIME}(o\left({\dfrac {f(n)}{\log f(n)}}\right))\). Let \(M_z\) be the Turing machine that decides \(L\) in \(o\left({\dfrac {f(n)}{\log f(n)}}\right)\) time.

Let the universal Turing machine \(\mathcal{U}(x, z)\) take time \(g(|x|)\) on \(x\). From the earlier introduction about universal Turing machines, we have \(g(n)=o(f(n))\). So, when \(y\) is large enough, \(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, so \(M_z(z, y')\ne M_z(z, y')\), a contradiction. Thus the assumption is false, and the deterministic time hierarchy theorem is proved.

Nondeterministic Time Hierarchy Theorem

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

From the nondeterministic time hierarchy theorem, we get \(\mathsf{NP}\subsetneq\mathsf{NEXPTIME}\).

Space Hierarchy Theorem

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

Here \(\mathsf{SPACE}\) can refer to \(\mathsf{DSPACE}\) or \(\mathsf{NSPACE}\).

From the space hierarchy theorem, we get \(\mathsf{PSPACE}\subsetneq\mathsf{EXPSPACE}\).

Savitch's Theorem

A deterministic Turing machine can simulate a nondeterministic Turing machine using at most the square of the space consumed by the latter (though possibly much more time), i.e.:

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}\), \(\mathsf{EXPSPACE}=\mathsf{NEXPSPACE}\).

P?=NP

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

If \(\mathsf{P}=\mathsf{NP}\), then \(\mathsf{NP}=\mathsf{co-NP}\) follows, but the converse does not hold (currently there is no method to prove \(\mathsf{P}=\mathsf{NP}\) based on \(\mathsf{NP}=\mathsf{co-NP}\)).

Why isn't NP?=co-NP obvious?

Since \(\mathsf{NP}\) problems and their corresponding \(\mathsf{co-NP}\) problems have opposite answers, it is easy to think: for a \(\mathsf{co-NP}\) problem, I just reverse the output of the nondeterministic Turing machine that solves its complement, and I solve the \(\mathsf{co-NP}\) problem, so \(\mathsf{NP}=\mathsf{co-NP}\).

Actually, the method described above can indeed solve that \(\mathsf{co-NP}\) problem, but it does not find a nondeterministic Turing machine to solve it: a Turing machine that reverses the output of a nondeterministic Turing machine is not itself a nondeterministic Turing machine. Because a nondeterministic Turing machine accepts on some branch and rejects on all branches; reversing its output means accepting on all branches and rejecting on one branch, which does not match the definition of a nondeterministic Turing machine. So being able to solve this \(\mathsf{co-NP}\) problem with such a machine does not make this \(\mathsf{co-NP}\) problem an \(\mathsf{NP}\) problem.

If \(\mathsf{P}=\mathsf{NP}\), we also get \(\mathsf{EXPTIME}=\mathsf{NEXPTIME}\).

If \(\mathsf{P}\ne\mathsf{NP}\), then NP-intermediate is non-empty.

References

Computational Complexity (1) Warming Up: Automata Models;
Computational Complexity (2) Turing Machine Computational Model;
Relevant entries on Wikipedia and their references.

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用