计算复杂性理论初步Ⅰ

TODO

图灵机

Defn（确定性图灵机，Turing Machine）：一个有着若干种寄存器状态，和一共 $k\,(k\ge 2)$ 条带子的计算机，并且每个带子上有一个指针在上面左右移动。其中第一条带子是输入带，上面存着输入的数据，可以读取指针位置的数据，但不允许往上面写数据。剩下 $k-1$ 条带子为工作带，读和写都可以操作。

更形式地说，图灵机 $M$ 是一个三元组 $(\Gamma,Q,\delta)$，其中：

• 有限集 $\Gamma$ 为字符集，且其包含两种特殊的字符：「空白符」$\Box$ 与「开始字符」$\triangleright$。
• 有限集 $Q$，包含 $M$ 的寄存器中可能出现的所有状态。此外，$Q$ 还包含一个开始状态 $q_{\text{start}}$ 和一个特定的终止状态 $q_{\text{halt}}$。
• 函数 $\delta:Q\times \Gamma^k\to Q\times \Gamma^{k-1}\times \{\text L,\text S,\text R\}^k$，刻画了 $M$ 在各个步骤中使用的规则。

不难看出这一定义是十分健壮的。字符集的大小（最小可以为 $4$，只包含 $\Box,\triangleright,0$ 和 $1$），带子数量的多少（最小只有一条输入带一条工作带），都不会对图灵机产生超过多项式的影响。

Fact（图灵机的编码表示）：图灵机本身是可以被编码的，你只需要编码 $\delta$ 函数即可，这本质上是在编码一张图。而且同一个图灵机可以有无穷多种编码方式（比如说在终止符后面一直添加无意义字符），而如果碰到了非法的编码直接将其指定为平凡图灵机即可。

对于一个图灵机 $M$，我们用 $\langle M\rangle$ 表示其编码（这一编码一般可以根据我们的需要任选）。而对于一个串 $\alpha$，我们用 $M_\alpha$ 表示编码表示为 $\alpha$ 的图灵机。

有了图灵机编码这一概念，我们可以引入通用图灵机的概念。这一概念的引入实际上更进一步阐释了之前图灵机定义的健壮性。

Thm（高效通用图灵机，Efficient Universal Turing Machine）：存在图灵机 $\mathcal U$ 使得 $\mathcal U(x,\alpha)=M_\alpha(x)$ 对于任意 $x,\alpha \in \{0,1\}^*$ 都成立。并且如果 $M_\alpha$ 在输入 $x$ 至多运行 $T$ 步后就停机，则 $\mathcal U(x,\alpha)$ 将在 $cT\log T$ 步内停机，其中 $c$ 是一个独立于 $|x|$ 而仅依赖于 $M_\alpha$ 字母表大小、带的数量于状态数量的常数。

这个定理是在说存在一个图灵机可以去模拟别的图灵机，而且时间上只有对数的损失。在后面我们还会看到，对于空间，则只有常数的损失。

还有一种特殊的图灵机，因其简单性，这种图灵机非常适合用于证明一些定理。

Defn（散漫图灵机，Oblivious Turing Machine）：称一个图灵机 $M$ 是散漫的，如果其具有这一性质：对于任何输入 $x\in \{0,1\}^*$ 和 $i\in \mathbb N$，在图灵机 $M$ 的第 $i$ 个步骤时，各条带的指针所处的位置仅是 $|x|$ 和 $i$ 的函数，而与 $x$ 除长度外具体内容无关。

可以证明任何图灵机都可以被一个散漫图灵机在平方时间内模拟，更进一步甚至可以在线性对数时间内模拟。

P 与 NP

Defn（类 $\textbf{DTIME}$）：设 $T:\mathbb N\to \mathbb N$ 是一个函数，称语言 $L\in \textbf{DTIME}(T(n))$ 当且仅当存在运行时间为 $cT(n)$ 的图灵机判定语言 $L$，其中 $c\ge 0$ 是常数。

而类 $\textbf P$ 被定义为 $\textbf P=\bigcup\limits_{c\ge 1}\textbf{DTIME}(n^c)$，也就是确定性图灵机在多项式时间内可以判定的语言的集合。

NP 完全性

Thm（判定 $\to$ 搜索）：若 $\textbf P=\textbf{NP}$，对于任意一个语言 $L\in \textbf{NP}$，设其的验证图灵机为 $M$。则存在一个多项时间的图灵机 $A$，在输入 $x\in L$ 上可以在输出带上输出 $x$ 关于 $M$ 的一个证明 $u$；在输入 $x\notin L$ 上会给出报告。

Proof： 先对 $\textbf{NP}$ 完全问题 $\text{SAT}$ 来考虑。设判定 $\text{SAT}$ 的多项式时间图灵机为 $M'$。

则对于任意一个纯布尔公式 $\varphi(x_1,\ldots,x_n)$：

先用 $M'$ 判断 $\varphi$ 是否可满足，如果不满足则直接报告。

如果可满足，我们再求出 $\varphi|_{x_1=0},\varphi|_{x_1=1}$（这两个公式都可以在多项式时间内由 $\varphi$ 化简为）。

两个中必有一个是可满足，令 $\varphi'(x'_1,\ldots,x'_{n-1})=\varphi|_{x_1=0/1}(x_1,x_2,\ldots,x_n)$，以这个 $\varphi'$ 为新的纯布尔公式迭代下去。

化简和调用 $M'$ 的次数都是线性次的（具体的，不超过 $2n$ 次），所以这个算法是多项式的，而且可以给出一个 $\varphi$ 的可满足赋值。$\Box$

这一定理的证明给出了 $\text{SAT}$ 问题的一个重要性质：向下自规约性，即多项式时间解决了比 $n$ 小的规模的问题，则可以多项式时间解决规模为 $n$ 的问题。事实上，$\textbf{NP}$ 完全问题都具有这一性质。

Cook-Levin 定理

一些 NP 完全问题

coNP、EXP 和 NEXP

$\textbf{coNP}$ 复杂类定义如下，一定程度上 $\textbf{coNP}$ 是 $\textbf{NP}$ 类的「补」：

$\textbf{coNP}=\{L\mid \overline{L}\in \textbf{NP}\}$

也可以用之前定义 $\textbf{NP}$ 时的 certification：对于任意语言 $L\in \{0,1\}^*$，称其属于 $\textbf{coNP}$ 当且仅当：存在一个多项式时间的图灵机 $M$ 和一个多项式 $p:\mathbb N\to \mathbb N$，使得：对于任意 $x\in \{0,1\}^*$

$x\in L\Longleftrightarrow \forall u\in \{0,1\}^{p(|x|)},\, M(x,u)=1$

要注意 $\text{coNP}\ne \{0,1\}^*\backslash \textbf{NP}$。

可以发现：$\textbf P\subseteq \textbf{NP}\cap \textbf{coNP}$。

下面语言是属于 $\textbf{coNP}$ 的，而且是 $\textbf{coNP}$ 完全的：

$\text{TAUTOLOGY} = \{\varphi\mid \varphi\text{ is a Boolean formula that is satisfied by every assignment}\}$

Thm：若 $\textbf P=\textbf{NP}$，则 $\textbf{NP}=\textbf{coNP}=\textbf P$。

Proof： 证明较为简单，略去。$\Box$

因为人们坚信 $\textbf P\ne \textbf{NP}$，故人们也坚信 $\textbf{NP}\ne \textbf{coNP}$。

$\textbf{EXP}$ 和 $\text{NEXP}$ 分别是确定性和非确定性的指数类：

$\textbf{EXP}=\bigcup_{c\ge 1} \textbf{DTIME}(2^{n^c}) \\ \textbf{NEXP}=\bigcup_{c\ge 1} \textbf{NTIME}(2^{n^c})$

下面这个定理展示了 $\textbf{EXP}$ 与 $\textbf{NEXP}$ 之间的关系与 $\textbf{P}$ 与 $\textbf{NP}$ 之间的关系非常类似。

Thm：如果 $\textbf{EXP}\ne \textbf{NEXP}$，则 $\textbf P\ne \textbf{NP}$。

Proof： 我们证明其逆否命题：如果 $\textbf{P}= \textbf{NP}$，则 $\textbf{EXP}=\textbf{NEXP}$。

设语言 $L\in \text{NTIME}(2^{n^c})$，我们构造一个新的语言 $L_{\text{pad}}$：

$L_{\text{pad}}=\{(x,1^{2^{|x|^c}})\mid x\in L \}$

这个语言是属于 $\textbf{NP}$ 的（先判断一个串长度对不对，然后再用解决 $L$ 的非确定性图灵机判断前面部分是不是属于 $L$ 的。因为又额外往里面加了若干个无用字符，所以是输入长度的多项式级别）。

又因为 $\textbf{NP}=\textbf P$，所以 $L_{\text{pad}}\in \textbf P$，用同样的方式倒着做一遍可以发现 $L\in \textbf{EXP}$。所以 $\textbf{NEXP}\subseteq \textbf{EXP}$。

故 $\textbf{NEXP}= \textbf{EXP}$。$\Box$

证明上面这个定理的计数叫做 padding（填充），往一个语言里填充若干无用的字符，这样可以让复杂度「降阶」。这个技术非常有用，可以用来证明复杂性「增高」后复杂类之间的相等关系。

不严格说：如果两种不同的计算资源在界限 $T$ 内求解了相同的一些问题，则用这两种不同的计算资源在界限 $T'$ 也将求解相同的另一些问题，其中 $T'>T$。

对角线方法

图灵机不可判定性初步

Thm（不可计算问题的存在性）：存在不可计算的问题。

Proof: 函数 $\text{UC}$ 定义如下：对于任意的 $\alpha\in \{0,1\}^*$：

• 如果 $M_\alpha(\alpha)=1$，则 $\text{UC}(\alpha)=0$。
• 否则（若 $M_\alpha(\alpha)$ 为其他值或进入无限循环）$\text{UC}(\alpha)=1$。

假设 $\text{UC}$ 是可计算的，则存在一个图灵机 $M$ 使得 $M(\alpha)=\text{UC}(\alpha)$ 对任意 $\alpha\in \{0,1\}^*$ 都成立。于是，特别的，有 $M(\langle M\rangle)=\text{UC}(\langle M\rangle)$ 成立。但这不可能，因为由 $\text{UC}$ 的定义可知：

$\text{UC}(\langle M\rangle)=1\Longleftrightarrow M(\langle M\rangle)\ne 1$

故得证。$\Box$

这种方法被成为对角线法，最初由 Cantor 用来证明实数集的不可数性。而在计算复杂性理论中，对角线法的关键工具就是图灵机的编码表示。

你可能会觉得上一个定理中的 $\text{UC}$ 很「人为」，那么我们再来介绍一个非常「实在」的不可判定问题——停机问题。

Thm（停机问题的不可判定性）：停机问题定义如下：

$\text{HALT}=\{(\alpha,x)\mid M_\alpha\text{ halts on input }x\}$

这一问题是不可判定的。

Proof： 假设 $\text{HALT}$ 可被图灵机 $M'$ 判定，我们构造如下图灵机 $M$ 可计算 $\text{UC}$，这与之前证明的定理矛盾了（规约）：

对于输入 $\alpha$，$M$ 运行 $M'(\alpha,\alpha)$。如果结果是 $0$（这意味着 $M_\alpha$ 在输入 $\alpha$ 上不停机），则 $M$ 输出 $1$。否则 $M$ 用通用图灵机计算 $b=M_\alpha(\alpha)$，如果 $b=1$ 则 $M$ 输出 $0$，否则输出 $1$。$\Box$

时间分层定理

接下来还有对角线法的若干运用，先来在时间层次上的应用。

Defn（时间可构造函数）：称一个函数 $f:\mathbb N\to \mathbb N$ 是时间可构造函数的，如果存在一个图灵机 $M$，在输入 $1^n$ 上，可以在 $O(f(n))$ 的时间内在带子上输出 $1^{f(n)}$（或者输出 $f(n)$ 的二进制表示，显然这两种输出都可以在 $O(f(n))$ 时间内互相转换）。

可以发现所有非常数的满足 $f(n)=o(n)$ 的函数都不是时间可构造函数，因为图灵机至少要读完整个输入。

引入「时间可构造」这一概念的目的主要是让图灵机可以知道较为轻松地自己到第几步了，否则可能会出现一些奇奇怪怪的问题。

Thm（确定性时间分层定理）：如果 $f,g$ 是满足 $f(n)\log (f(n))=o(g(n))$ 的时间可构造函数，则：

$\textbf{DTIME}(f(n))\subset \textbf{DTIME}(g(n))$

Proof： 考虑这样的一个图灵机 $D$：在输入 $x$ 上，使用通用图灵机 $\mathcal U$ 模拟 $M_x$ 在 $x$ 上执行的前 $h(|x|)$ 个步骤，其中函数 $h_\mathbb N\to \mathbb N$ 满足 $g(n)=\Theta(h(n)\log(h(n)))$，则 $f(n)=o(h(n))$。此时如果 $\mathcal U$ 输出 $\{0,1\}$ 中的一个数 $b$，则 $D$ 输出 $1-b$。否则 $D$ 输出 $0$。

设 $D$ 判定的语言为 $L$。显然 $L\in \textbf{DTIME}(g(n))$，下证明 $L\notin \textbf{DTIME}(f(n))$：

如果 $L\in \textbf{DTIME}(f(n))$，则存在一个运行时间为 $cf(n)$ 的图灵机 $M$。

因为 $f(n)=o(h(n))$，所以存在一个 $n_0\in \mathbb N$，使得 $h(n)\log(h(n))>c\log c f(n)\log(f(n))$。

取 $\langle M\rangle$ 足够长使得上面的不等式满足，则 $M$ 在输入 $\langle M\rangle$ 上不到 $h(|\langle M\rangle|)\log(h(|\langle M\rangle|))$ 步就已经输出了一个答案 $b\in \{0,1\}$。但是根据 $D$ 的定义，$D$ 会在输入 $\langle M\rangle$ 上输出 $1-b$，则 $M(\langle M\rangle)\ne D(\langle M\rangle)$，矛盾。

故得证。$\Box$

Thm（非确定性时间分层定理）：如果 $f,g$ 是满足 $f(n+1)=o(g(n))$ 的时间可构造函数，则：

$\textbf{NTIME}(f(n))\subset \textbf{NTIME}(g(n))$

Proof：

Thm（非平凡时间不可构造函数的存在性）：存在一个可计算的函数 $T:\mathbb N\to \mathbb N$，使得 $T(n)\ge n$ 且 $T$ 不是时间可构造的。

Proof： 令 $L$ 是满足如下条件的语言：$L\in \textbf{DTIME}(n^2)$ 但 $L\notin \textbf{DTIME}(n)$。由时间分层定理，这样的语言 $L$ 存在。再设 $M$ 是判定 $L$ 的图灵机。

则如下函数就不是时间可构造的，但是是可计算的：

$T(n)=n+M(1^n)$

这是因为 $M$ 运行时间为 $\Theta(n^2)$，但是 $T(n)=\Theta(n)$。故得证。$\Box$

NP 非完全问题的存在性

Thm（Ladner 定理）：假设 $\textbf P\ne \textbf{NP}$，则存在一个语言 $L\in \textbf{NP}\backslash \textbf P$，且 $L$ 不是 $\textbf{NP}$ 完全的。

Proof：

神谕图灵机与相对性

Defn（神谕图灵机，Oracle Turing Machine）：神谕图灵机是一个图灵机 $M$，它有一条称作神谕带的特殊可读可写带和三个特殊状态 $q_{\text{query}},q_{\text{yes}},q_{\text{no}}$。要运行图灵机 $M$，除了为 $M$ 指定输入外，还需要为 $M$ 指定一个用作神谕的语言 $O\subseteq \{0,1\}^*$。运行过程中，一旦 $M$ 进入状态 $q_{\text{query}}$，机器便立刻根据神谕带上的内容 $q$ 决定下一个状态：如果 $q\in O$ 则机器进入 $q_{\text{yes}}$，否则进入 $q_{\text{no}}$。无论 $O$ 是何种语言，判定 $q$ 是否属于 $O$ 均仅用一个计算步骤。如果 $M$ 是一个神谕图灵机，$O\subseteq \{0,1\}^*$ 是一种语言，则将 $M$ 以 $O$ 为神谕在输入 $x$ 上得到的输出即为 $M^O(x)$。

神谕图灵机是如下这类算法的抽象：允许将其他函数作为黑盒例程调用而不用关心函数的具体实现。

下面这一定理表明：不管 $\textbf P=\textbf{NP}$、$\textbf P\ne \textbf{NP}$ 哪一个成立，其都不是相对结论。

Thm（$\textbf P\text{ vs }\textbf{NP}$ 的非相对性）：存在神谕 $A$ 和 $B$，使得 $\textbf P^A=\textbf{NP}^A$ 和 $\textbf P^B\ne \textbf{NP}^B$。

Proof： 令 $A$ 为任何一个 $\textbf{NP}$ 完全问题即可得到 $\textbf P^A=\textbf{NP}^A=\textbf{NP}$。

对于任何语言 $B$，我们用 $U_B$ 表示如下一元语言：

$U_B=\{1^n\mid \text{some string of length }n\text{ is in }B\}$

对于任何语言 $B$，$U_B$ 都是属于 $\textbf{NP}^B$ 的。因为对于任何输入 $1^n$，我们都可以非确定的在多项式时间内搜索 $\{0,1\}^n$ 里的所有串。

我们考虑构造 $B$ 使得 $U_B\notin \textbf P^B$，方法如下：

我们通过一系列阶段来构造 $B$，其中第 $i$ 个阶段我们要确保 $M_i$ 无法在 $2^n/10$ 的时间内判定 $U_B$。在把所有自然数 $i$ 都考虑过后，这样构造出来的 $B$ 便使得 $U_B$ 无法被任何神谕图灵机在 $f(n)=o(2^n)$ 时间内判定，特别的，$U_B\notin \textbf P^B$。

假设我们已经执行完了第 $1$ 到 $i-1$ 阶段，在第 $i$ 阶段我们做如下事情：

令 $S_i$ 为如下集合：

$S_i=\{x\mid \exist j\in [i-1]\text{ s.t. }M_j\text{ asks the question "Is }x\text{ in }B\text{?" in the first }2^{n_j}/10\text{ steps}\}$

也就是说 $S_i$ 是在所有的在第 $i$ 个阶段之前，那些个被扔到神谕 $B$ 里面被询问的串的集合。显然 $S_i$ 是有限的（因为 $2^{n_j}/10$ 的和是有限的）。

令 $n_i=\max\limits_{x\in S_i}\{|x|\}+10$，我们让 $M_i$ 在输入 $1^{n_i}$ 上去跑，而神谕为 $B$。

如果 $M_i$ 的运行时间超过了 $2^{n_i}/10$，或者干脆不停机了，则 $M_i$ 确实无法在 $2^n/10$ 时间内判定 $U_B$，可以直接结束这一阶段。

如果 $M_i$ 在 $2^{n_i}/10$ 步以内输出了，我们考虑往 $B$ 中再添加若干个长度为 $n_i$ 的串。因为 $n_i>\max\limits_{x\in S_i}\{|x|\}$，从而 $B$ 更新不会影响前面阶段中讨论得到的 $M_j^B(1^{n_j})$ 的值（因为 $M_j^B$ 在输入 $1^{n_j}$ 上执行根本用不到这么长的串）。

而这些个新加的串是这样被选出来的：

• 如果 $M_i^B(1^{n_i})=1$，因为 $B$ 里面没有长度为 $n_i$ 的串，所以 $U_B(1^{n_i})=0$，故 $M_i$ 判断错了，不需要往 $B$ 里面加任何串。

• 如果 $M_i^B(1^{n_i})=0$。因为 $M_i$ 至多运行 $2^{n_i}/10$ 步，所以其至多取神谕里面查询 $2^{n_i}/10$ 种串。

  又因为 $2^{n_i}/10<2^{n_i}$，故必有一个长度为 $n_i$ 的串 $s$，满足 $s$ 没有被 $M_i^B$ 在输入 $1^{n_i}$ 上查询过，而且也没有被前面的 $M_j^B(1^{n_j})$ 查询过。

  我们把 $s$ 加入到 $B$ 中，这不会影响 $M_j^B(1^{n_j})\,(j\in [i])$，但是这时候 $U_B(1^{n_i})$ 变为 $1$，$M_i$ 判断错了。

这样 $B$ 的构造就完成了。

可以看到，$B$ 是属于 $\textbf{EXP}$ 的，只需要模拟如上的计算过程即可。$\Box$

空间复杂度

格局图

Defn（空间受限计算）：设 $S:\mathbb N\to \mathbb N$。如果存在常数 $c$ 和判定 $L$ 的图灵机 $M$，使得对任意长度为 $n$ 的输入，$M$ 完成计算的过程中 $M$ 的带头至多访问除输入带之外的 $cS(n)$ 个存储单元，则称 $L\in \textbf{SPACE}(S(n))$。

类似地，如果存在判定 $L$ 的非确定型图灵机 $M$ 使得对任意长度为 $n$ 的输入，$M$ 完成计算的过程中在任意非确定型选择上至多使用 $cS(n)$ 个非空白存储单元，则称 $L\in \textbf{NSPACE}(S(n))$。

时空复杂度有一定联系，如下定理所示。令人以为的是，这一定理是目前唯一已知的时空关系，该结论的改进或许会成为重大的研究成果。

Thm（时空关系）：对于任意空间可构造函数 $S: \mathbb N\to \mathbb N$ 有：

$\textbf{DTIME}(S(n))\subseteq \textbf{SPACE}(S(n))\subseteq \textbf{NSPACE}(S(n))\subseteq \textbf{DTIME}(2^{O(S(n))})$

为证明此定理，我们引入格局图这一概念：

Defn（格局图，Configuration Graph）：令 $M$ 是一个确定型或非确定型图灵机。图灵机 $M$ 在其执行过程中的某个时刻上的格局由此时所有带上的非空白符号、机器的状态和所有带头的位置构成。

对于任意 $S(n)$ 空间图灵机 $M$ 和输入 $x\in \{0,1\}^*$，$M$ 在输入 $x$ 上的格局图是一个有向图，记为 $G_{M,x}$，其顶点为：在输入 $x$ 且所有工作带至多包含 $S(n)$ 个非空白存储单元的条件下 $M$ 的所有可能的格局。

如果从格局 $C$ 开始，根据 $M$ 的转移函数，通过一个计算步骤可以到达格局 $C'$，则从 $C$ 到 $C'$ 有一条有向边。

如果 $M$ 是确定型图灵机，则 $G$ 的出度为 $1$。如果 $M$ 是非确定型图灵机，则 $G$ 的出度为 $2$。

Fact：

空间分层定理

一些个比较重要空间复杂类：

$\textbf{PSPACE}=\bigcup_{c\ge 1}\textbf{SPACE}(n^c) \\ \textbf{NPSPACE}=\bigcup_{c\ge 1}\textbf{NSPACE}(n^c) \\ \textbf{L}=\textbf{SPACE}(\log n) \\ \textbf{NL}=\textbf{NSPACE}(\log n)$

Thm（空间通用图灵机）：存在图灵机 $\mathcal S$ 使得对于任意串 $\alpha$ 和输入 $x$，如果 $M_\alpha$ 以 $x$ 为输入时在使用工作带上第 $t$ 个存储单元之前停机，则 $\mathcal S(\alpha,x)=M_\alpha(x)$，并且 $\mathcal S$ 至多使用工作带上的 $ct$ 个存储单元，其中 $c$ 是仅依赖 $M_\alpha$ 的常数。

Thm（空间分层定理）：设 $f,g$ 是满足 $f(n)=o(g(n))$ 的空间可构造函数，则：

$\textbf{SPACE}(f(n))\subset \textbf{SPACE}(g(n))$

Proof： 仿照确定性时间分层定理以及空间通用图灵机的结论，容易证明此结论。$\Box$

TQBF 问题与 Savitch 定理

Defn（量化布尔公式与 $\text{TBQF}$ 问题）：量化布尔公式（QBF）是形如 $Q_1x_1Q_2x_2\cdots Q_nx_n\,\varphi(x_1,\ldots,x_n)$ 的布尔公式，其中任意 $Q_i$ 是两次 $\forall$ 或 $\exist$，变量 $x_1,\ldots,x_n$ 的值域为 $\{0,1\}$，$\varphi$ 是一个纯布尔公式（即不含量词的布尔公式）。

而 $\text{TQBF}$ 问题定义如下：

$\text{TQBF}=\{\phi\mid \phi\text{ is a satisfiable QBF}\}$

Thm：$\text{TQBF}$ 是 $\textbf{PSPACE}$ 完全的。

Proof：

注意到上述定理的证明中并没有要求格局图的出度为 $1$，这揭示了一个重要的事实：$\text{TQBF}$ 也是 $\textbf{NPSPCAE}$ 完全的，于是乎 $\textbf{PSPACE}=\textbf{NPSPACE}$。这是非常神奇的，因为人们坚信 $\textbf P\ne \textbf{NP}$。

推广上一定理的证明，我们可以得到 Savitch 定理。

Thm（Savitch 定理）：对于任意满足 $S(n)\ge \log n$ 的空间可构造函数 $S:\mathbb N\to\mathbb N$，均有：

$\textbf{NSPACE}(S(n))\subseteq \textbf{SPACE}(S(n))$

这一定理表明 $\textbf{PSPACE}=\textbf{NPSPACE}$，这与 $\textbf{P}$ 和 $\textbf{NP}$ 的关系很不一样。

PSPACE 的本质：最佳博弈策略

NL 完全性与 NL=coNL

$\text{PATH}$ 是如下语言：

$\text{PATH}=\{\langle G,s,t \rangle\mid \text{There is a path from }s\text{ to }t\text{ in the directed graph }G\}$

$\text{PATH}$ 是属于 $\textbf{NL}$ 的，因为如果有路径则长度至多为 $|V|$，所以可以通过多项式长度的非确定选择来模拟搜索。

$\text{PATH}$ 是否属于 $\text{L}$ 还未有定论。但非常惊人的是，如果限定 $G$ 为无向图，得到的新问题 $\text{UPATH}$ 是属于 $\text{L}$ 的。其证明是随机算法的去随机化（可见：）。

Defn（隐性对数 Karp 规约）：

Thm（$\textbf{NL}$ 完全性）：$\text{PATH}$ 是 $\textbf{NL}$ 完全的。

Proof：

Thm（Immerman-Szelepcséyi 定理）：$\overline{\text{PATH}}\in \textbf{NL}$。

Proof：

通过将 $\text{PATH}$ 问题中的图设定为非确定性图灵机的格局图，我们可以得到如下推论。

Cor：对于任意空间可构造函数 $S:\mathbb N\to \mathbb N$，有 $\textbf{NSPACE}(S(n))=\textbf{coNSPACE}(S(n))$。

一些问题

Thm（一元语言的非 $\textbf{NP}$ 完全性）：假设存在一个一元语言 $L\in \{1\}^*$ 是 $\textbf{NP}$ 完全的，则 $\textbf{P}=\textbf{NP}$。

Proof： 假设 $L\in \{1\}^*$ 是 $\textbf{NP}$ 完全的，则存在一个函数 $f:\{0,1\}^*\to\{0,1\}^*$，与一个多项式函数 $p:\mathbb N\to \mathbb N$，使得 $\forall x\in \{0,1\}^*$：

$x\in \text{SAT} \Longleftrightarrow f(x)\in L$

且 $|f(x)|\le p(|x|)$。

我们进行一个记忆化搜索，可以判断一个纯布尔公式 $\varphi$ 是否是可满足的：

我们开一个全局的哈希表 $H$，初始为空。

再定义一个函数

上述论断可以从一元语言扩展到任意的稀疏语言：

Defn（稀疏语言，Sparse Language）：称 $L\in \{0,1\}^*$ 是稀疏的，当且仅当：存在一个多项式 $p:\mathbb N\to \mathbb N$，满足对于任意的 $n\in \mathbb N^+$，有：

$|L\cap \{0,1\}^n|\le p(n)$

Thm（Mahaney 定理）：假设存在一个稀疏语言 $L\in \{0,1\}^*$ 是 $\textbf{NP}$ 完全的，则 $\textbf{P}=\textbf{NP}$。

实际上上述定理的陈述中「$\textbf{NP}$ 完全」可以改为「$\textbf{NP}$ 难」，这是因为一个 $\textbf{NP}$ 难的稀疏语言可以导出一个 $\textbf{NP}$ 完全的语言。

---

Thm：证明 $\textbf{SPACE}(n)\ne \textbf{NP}$（我们暂且不知道是否有一个包含另一个）。

Proof：