Complexity Theory 中一些基础定理的证明

今天的又蓝又白，结果看上去灰蒙蒙的。

# HALT 的不可判定性

证明：使用对角线方法（Diagonalization），即考虑$M(\langle M\rangle)$ 的情况，着手证明。

首先，考虑下列函数：

$$UC(x)=\begin{cases} 0 & if\;M_x(x)\;halts\;and\;output\;1\\ 1 &otherwise \end{cases}$$

那么先证明下述语言是不可判定的：

$$L_{UC}=\{x\;|\;UC(x)=1\}$$

反设存在一个图灵机$M$ 判定$L_{UC}$，那么我们考虑$M$ 在输入$\langle M\rangle$ 上会怎样：

• 若$M(\langle M\rangle)$ 停机了。

  • 若$M(\langle M\rangle)=0$，由于$M$ 判定$L_{UC}$，故$\langle M\rangle\notin L_{UC}$，即$UC(\langle M\rangle)=0$。

    根据$UC$ 函数的定义，$UC(\langle M\rangle)=0$ 当且仅当$M(\langle M\rangle)$ “halts and output 1”，矛盾。

  • 若$M(\langle M\rangle)=1$，由于$M$ 判定$L_{UC}$，故$\langle M\rangle\in L_{UC}$，即$UC(\langle M\rangle)=1$。

    根据$UC$ 函数的定义，$UC(\langle M\rangle)=1$ 当且仅当$M(\langle M\rangle)$ 不停机或者输出 0。由于假设$M(\langle M\rangle)$ 停机了，故$M(\langle M\rangle)=0$，矛盾。

• 若$M(\langle M\rangle)$ 不停机，与 “$M$ 判断$L_{UC}$” 矛盾，即有输入$\langle M\rangle$ 导致$M$ 无法判断。

证毕。

这个定理我的理解其实是 “任何尝试去判定$L_{UC}$ 的图灵机$M$，都一定会存在某个输入$input=\langle M\rangle$，使得$M$ 不停机，故无法判断它。”

下面我们证明$L_{HALT}$ 的不可判定性。其实证明本质是，一旦我们可以提前得知是否停机，我们就可以判定$L_{UC}$，而$L_{UC}$ 的不可判定性也恰恰来自于是否停机。

反设存在一个图灵机$M$ 判定$L_{HALT}$，那么我们可以构造一个图灵机$M'$ 去判定$L_{UC}$：

• 对于输入$x$，使用$M(\langle x,x\rangle)$ 去判定$M_x(x)$ 是否停机。
  • 若不停机，则$M'$ 直接输出 1。
  • 若停机，则让$M'$ 去模拟$M_x$，并输出与$M_x(x)$ 相反的结果。

很显然，上述图灵机$M'$ 判定了$L_{UC}$，矛盾。

故证毕。

# Cook-Levin Theorem: Boolean Circuit 的通用性

Proof：首先$CIRCUIT-SAT\in NP$ 是显而易见的，所以我们证明的重点在于，$\forall L\in NP,L\leq_m^p CIRCUIT-SAT$。

这个定理初看非常困难，因为要证明$\forall L\in NP$。但实际上，根据$NP$ 问题的定义，实际上就是要证明图灵机向 Boolean Circuit 的规约。

考虑$L\in NP$，故存在一个判定图灵机$V$，使得$\forall x\in L,\exists y,V(x,y)=1$。

直观地理解，要判定$x\in ? L$，实际上就是要知道是否存在一个$y$ 满足$V(x,y)=1$，其实就对应了可满足问题是否存在一个$y$ 满足 Circuit 的输出是 1，而这个 Circuit 就对应了$V$，它的输入是$x,y$，前者是已知的，后者是可以自由 assign 的。

---

我们不妨假设$x=1011$，看一下如何构造一个 Circuit $C$，使得$x\in L\Leftrightarrow C$ is satisfiable.

首先，我们知道存在一个$y$ 和图灵机$V$，使得$V$ 在$O(T(n))$ 时间内输出$V(x,y)=1$。那么我们考虑$V$ 的每一步，$V$ 每操作一步，关键的信息就是：读写头位置 + 带子上的内容。而我们把读写头位置 + 带子上的内容编码成一个二进制串，譬如$0@111$ 就表示，带子上内容为 “0111”，读写头指向 "@" 右侧的字符。

那么我们考虑把图灵机的每一步操作，都等价为一层的 Circuit：

其中有一个重要论断：tape 上某个单元格的内容，在一步操作后会变成什么，只和上一步该单元格附近的单元格内容和图灵机的转移函数有关。注意，其实也与读写头位置有关，但是读写头位置被编进了 tape 的内容。

注意，核心就在于 “附近”，实际上是常数个，严格来说应为 4 个。故只需要$n-4=O(n)$ 个数的 circuit（上图中的小方块），就可以模拟单步的图灵机操作。

注意，任意的$\{0,1\}^4\rightarrow\{0,1\}^4$ 函数都可以用常数个 Boolean 门来模拟。如果需要 "@" 符号，可以使用替换字符集的编码技巧，在此不具体讨论。

故实际上，上右图中的 circuit 结构，只跟图灵机$V$ 的转移函数有关，而且这个 circuit 模拟了图灵机的行为。

我们把 circuit 输入的左侧部分改为$x$，就可以通过 circuit 是否可满足，来判断是否存在$y$，使得$V(x,y)=1$ 了。

故实际上，给定$L\in NP$ 的一个判断图灵机$V$，我们就可以构造一个 circuit。然后对于输入$x$，将 circuit 的左侧改为$x$，那么此时$x\in L$ 就等价于 circuit 的可满足性了，完毕。

显然地，circuit 的复杂性在$O(T(n)^2)$ 级别，也没有到指数复杂性。

# $P=NP\Rightarrow EXP=NEXP$ 的证明技巧: Padding

Proof：假设$P=NP$。$EXP\subseteq NEXP$ 是显然的，我们着手证明$NEXP\subseteq EXP$。

对于$L\in NEXP$，我们人为地构造一个语言：

$$L_{pad}=\{\langle x,1^{2^{|x|^k}}\rangle\;|\;x\in L\}$$

其实就是对$L$ 中的字符串，后面加一个长度为$2^{|x|^k}$，全为 1 的 padding。$k$ 对证明不是很重要。

我们可以证明，padding 后的这个语言$L_{pad}\in NP$。假设存在一个非确定性图灵机$M$ 去判定$L$。

我们构造一个图灵机$M'$ 去判定$L_{pad}$：

1. 对于输入$y$，判断$y$ 的形式是否满足$y=\langle x,1^{2^{|x|^k}}\rangle$，若不是，则拒绝。

   记$n=|y|=O(2^{|x|^k})$，那么这一步需要的复杂度为$O(poly(n))$。

2. 提取出$x$，然后去模拟非确定性图灵机$M$。并输出$M$ 的结果。由于$L\in NEXP$，故$M$ 所需步骤为$O(poly(|x|)2^{|x|^k})=O(poly(logn)\cdot n)$，对于$M'$ 来说，就是多项式级别。

故综上，$L_{pad}\in NP$。因为$P=NP$，故$L_{pad}\in P$，故存在一个确定型图灵机$M^*$ 判定$L_{pad}$。下面我们证明$L\in EXP$。

构造这样一个图灵机：

1. 对于输入$x$，先 pad $2^{|x|^k}$ 个 1。这一步复杂度为$O(2^{|x|^k})$。
2. 模拟$M^*$ 去判定$x$。这一步复杂度也为指数级。

综上，$L\in EXP$。证毕