04 问题的难度

根据加速定理，我们明白了我们必须对算法定义复杂性而不能对问题定义复杂性。然而，直观上确实存在不同问题的难易程度(hardness)之分。有的问题只需要扫描一遍输入就可以求出，有的问题似乎除了暴力搜索之外没有好办法。那么我们应该如何比较不同问题之间的难度呢？（除非特殊说明，我们所说的“问题”就是指判定性问题，一个问题$L$是$\{0,1\}^\ast$的一个子集）

归约(Reduction)

$m$-归约(Many-One Reduction)

比较问题难度的最直接也是最本质的方法就是归约(reduction)。当我们要判定一个问题$A$时，如果我们能找到一个可计算全函数$f$使得$x\in A\iff f(x)\in B$，那么我们就可以对于每个输入$x$做一步计算$f(x)$而把问题转化为$B$。如果这样的$f$存在，我们就称问题$A$能归约成问题$B$。这是最基本的归约形式，称为$m$-归约，记为$A\leq_mB$。如果$A\leq_m B$，则说明只要我们有办法解决$B$就一定能解决$A$，所以$B$是一个比$A$难或至少$A$不比$B$更难。

$m$-归约和我们直观上理解的“归约”还是有一些差距的。我们从图灵机的角度看$m$-归约，它说的实际上是：如果存在一个判定$B$的图灵机$\mathbb{M}_B$，存在一个计算$f$的图灵机$\mathbb{M}_f$，那么我们可以构造一台判定$A$的图灵机$\mathbb{M}_A$，方法是对于每个输入$x$，先调用子程序$\mathbb{M}_f$计算得到$f(x)$，在把$f(x)$作为$\mathbb{M}_B$的输入，那么$\mathbb{M}_B$的输出刚好就是判定$x\in A$的正确答案。注意到在这个过程中，我们只允许$\mathbb{M}_A$调用一次子程序$\mathbb{M}_B$，并且必须是在程序末尾调用。而在我们直观上理解的“归约”中，我们应当可以反复调用$\mathbb{M}_B$多次，并且不一定是在结尾时调用。

图灵归约(Turing Reduction)

为了让归约的定义更加直观，我们引入神谕图灵机(oracle Turing machine)的概念。一台带有问题$L$的神谕图灵机可以在运行过程中用一步计算的代价询问是否有$x\in L$并获得正确回答（因此，这也是一个假想模型）。具体的，定义神谕图灵机$\mathbb{M}^L$上有一条神谕带，它有三个额外的运行状态$q_{query},q_{yes},q_{no}$，某时刻如果神谕带上写着$z$，并且图灵机进入状态$q_{query}$，那么下一步如果$z\in L$就会进入状态$q_{yes}$，否则就会进入状态$q_{no}$。

如果存在一台神谕图灵机$\mathbb{M}^B$使得$\mathbb{M}^B$能够判定问题$A$，就称$A$能图灵归约到$B$，记为$A\leq_T B$。由此可见，图灵归约可以反复调用判定$B$的子程序，并且可以在调用的间隙做计算。这符合我们对归约的直观印象。

多项式归约(Polynomial Reducton)

在复杂性中，我们特别关心多项式时间可完成的归约（高效归约）。

和$m$-归约对应，我们定义Karp归约：如果存在一个多项式时间可计算全函数$f$使得$x\in A\iff f(x)\in B$，那么就称问题$A$能Karp归约为问题$B$。记为$A\leq_K B$。

和图灵归约对应，我们定义Cook归约：如果存在一台多项式运行时间的神谕图灵机$\mathbb{M}_P^B$使得$\mathbb{M}_P^B$能够判定问题$A$，就称$A$能Cook归约到$B$，记为$A\leq_C B$。（如果我们定义复杂性类$\text{P}^L$为所有带神谕$L$的多项式时间图灵机能判定的问题集合，那么“存在一台多项式运行时间的神谕图灵机$\mathbb{M}_P^B$使得$\mathbb{M}_P^B$能够判定问题$A$”可以写为$A\in \text{P}^B$）

显然，归约有传递性。因此我们可以良好的比较问题间的大小。比较的方式可以是$m$-归约，也可以是图灵归约、多项式归约。不同的比较方法会导致不同的难易指标。

时间意义的难度

在时间复杂性中，研究$\text{P}$是否等于$\text{NP}$时，我们可以采取这样的思路：如果在多项式归约意义下$\text{NP}$中最难的那个问题能被多项式解决，那么我们也就证明了$\text{P}=\text{NP}$。

NP-completeness

如果存在问题$B$使得$\forall A\in \text{NP}$，$A\leq_K B$，那么就称$B$是一个NP-hard问题（注意这里我们用的是Karp归约，也即只能调用一次子程序的多项式归约）。如果$B$是NP-hard的并且$B\in \text{NP}$，那么就称$B$是NP-complete的。定义问题类$\text{NPC}$是所有NP-complete问题的集合。

Cook-Levin定理

Cook与Levin证明了，$\texttt{SAT}$问题是NP-complete的。

$\texttt{SAT}$问题是一个合取范式(Conjunctive Normal Form, CNF)的集合（一个CNF也就是一个形如$\bigwedge\limits_{i}\left(\bigvee\limits_{j}v_{i_j}\right)$的布尔公式），其中所有的CNF都是存在一组使其逻辑值为真的变量赋值的。

与CNF相对，析取范式(Disjunctive Normal Form, DNF)的可满足性问题是容易的，一个DNF也就是一个形如$\bigvee\limits_{i}\left(\bigwedge\limits_{j}v_{i_j}\right)$的布尔公式。要使他为真，只需存在一个clause为真，而一个clause为真当且仅当每个literal都为真。显然只需遍历一遍DNF并记录literal看是否会推出矛盾，就可以判定DNF是否是可满足的。因此DNF的SAT问题有多项式时间算法。Cook-Leven定理就是要指出，CNF的SAT问题是没有多项式时间算法的，除非$\text{P}=\text{NP}$。

证明：

显然，SAT问题是多项式可验证的。因此$\texttt{SAT}\in\text{NP}$。因此只需证明$\texttt{SAT}$是$\text{NP}$-hard，也即$\forall L\in\text{NP}$，$L\leq_K \texttt{SAT}$。

利用$\text{NP}$在确定性图灵机下的等价定义，$L\in \text{NP}$当且仅当存在多项式时间图灵机$\mathbb{M}$满足$\exists u \in \{0,1\}^{p(|x|)},\mathbb{M}(x,u)=1$。我们意识到，要把这一命题归约到$\texttt{SAT}$，实际就是要用布尔逻辑刻画$\mathbb{M}(x,u)=1$（由于只需考虑可满足性，我们可以忽略存在量词）。所以，$\texttt{SAT}$问题是不是$\text{NP}$的这一问题的实质是，是否存在对于“计算”的逻辑刻画？

我们要用一个CNF来刻画$\mathbb{M}(x,u)=1$。设$\mathbb{M}$有时间函数$T(n)$，那么对于输入$x$，我们可以默认图灵机的输入长度是定长$O(T(|x|))$的。输入变量个数固定的布尔函数可以等价转化为CNF（设$f:\{0,1\}^*\to \{0,1\}$，令$f(x)=\bigvee\limits_{f(\alpha)=1}C_{\alpha}$即可，其中$C_\alpha$是一个合取的clause，表示输入变量是否构成$\alpha$），因此我们只需考虑如何把$\mathbb{M}(x,u)=1$转化为布尔函数。

我们可以不失一般性假设图灵机是单带的（单带图灵机可以多项式模拟任意带图灵机）。这样，我们只需找到一种逻辑刻画，可以依照转移函数，描述图灵机的状态、每一状态下纸带上每一格的内容和读写头的位置。我们可以让每一格都用若干布尔变量来表示，一部分描述当前格上的内容（$\log|\Gamma|$位），一部分描述当前格是否有读写头所指（$1$位），另外我们在每一格上都编码记录当前图灵机的状态（$\log |Q|$）。这样做的好处是，对于相邻两个状态，要刻画下一状态上某一格上的布尔变量，只需考虑上一状态中该格的布尔变量及其左右两格的布尔变量（因为读写头要么不动，要么只会移动一格）。这一刻画只需依据转移函数，用一个布尔函数描述。具体细节就不展开了。

证毕。

---

Karp证明了$\texttt{SAT}$问题可以Karp归约到21个组合问题，包括3$\texttt{SAT}$、图的点覆盖问题、01整数规划等等耳熟能详的问题。只要证明这些问题中的任何一个有多项式算法，就能证明$\text{P}=\text{NP}$。

一个有趣的问题是，如果$\text{P}\neq\text{NP}$，那么$\text{NP}\setminus\text{P}$中是否含有除了NP-complete问题以外的其它问题？Ladner定理指出，$\text{NP}\setminus\text{P}$中确实含有除了NP-complete问题以外的其它问题，并且这样的问题数量是无穷多的。证明略。

空间意义的难度

类比时间复杂性，在那里我们可以用最小的时间资源类$\text{P}$来定义归约，从而能够比较不同问题在时间复杂性意义下的难度。那么对于空间复杂性，我们能否用最小的空间资源类$\text{L}$来定义归约，从而比较不同问题在空间复杂性意义下的难度呢？

如果存在一个对数空间可计算的全函数$f$使得$x\in A\iff f(x)\in B$，那么就称问题$A$能对数空间归约为问题$B$。记为$A\leq_L B$。

以上定义等价于：如果存在一个隐式对数空间可计算(implicitly logspace computable)全函数$f$使得$x\in A\iff f(x)\in B$，那么就称问题$A$能对数空间归约为问题$B$。记为$A\leq_L B$。其中，$f$是隐式对数空间可计算的当且仅当 ①$\forall x,|f(x)|$是关于$|x|$的多项式长的；②输入$x,i$，判定是否成立$i\leq |f(x)|$的问题只需要对数空间；③输入$x,i$，判定是否成立$f(x)$的第$i$位是1只需要对数空间。这三点定义“隐式地”保证了$f$的计算只需要用到对数空间，因为对于每个$x$，计算$f(x)$的每一位以及计算$f(x)$的位数都只需要对数空间。

如果存在问题$B$使得$\forall A\in \text{L}$，$A\leq_L B$，那么就称$B$是一个L-hard问题。如果$B$是L-hard的并且$B\in \text{L}$，那么就称$B$是L-complete的。类似的，可以定义NL-hard，NL-complete，PSPACE-hard，PSPACE-complete等等（都是用对数空间归约定义）。

可达性问题(Reachability Problem)是指：给定一张有向图和有向图上两个节点，判定两点间是否存在一条可达路径。可以证明，可达性问题是NL-complete问题，也即所有非确定性图灵机能在对数空间判定的问题都可以归约为可达性问题，并且可达性问题本身也只需要非确定性图灵机在对数空间内判定。方法是，从起点出发，每次用非确定性图灵机猜测其一个邻居，然后释放原节点的空间。这样重复$n$次，就可以判定是否到达。由于我们只需要一个计数器记录当前节点，因此是对数空间的。

量化布尔公式问题(Quantified Boolean Formula Problem, QBF Problem)定义为所有恒真的量化布尔公式$Q_1x_1Q_2x_2\cdots Q_kx_k\varphi(x_1,\cdots,x_k)$的集合，其中$Q_1\cdots Q_k$要么是$\forall,\exists,\forall ,\exists,\cdots$要么是$\exists,\forall,\exists,\forall,\cdots$，$x_1,\cdots,x_n$是布尔变量，$\varphi$是任意的布尔函数。Stockmeyer-Meyer定理指出，QBF问题是PSPACE-complete的。

Savitch定理指出：对于空间可构造函数$S(n)$，始终成立$\text{NSPACE}(S(n))\subseteq \text{SPACE}((S(n))^2)$。也即非确定性图灵机在空间$S(n)$下能判定的问题一定能用确定性图灵机在$S(n)^2$的空间内判定。这里的平方使得我们能把多项式空间的确定性图灵机和多项式空间的非确定性图灵机等价起来。当我们要证明一个问题可以用确定性图灵机在多项式空间内判定时，只需证明这个问题可以用非确定性图灵机在多项式空间内判定。这意味着$\text{PSPACE}=\text{NPSPACE}$。这是一个有点反直觉的结论，侧面反映出多项式空间类已经是一个极其广大的类了。

我们知道$\text{PSPACE}=\overline{\text{PSPACE}}$，因为对于确定性图灵机，如果一个问题能在多项式空间解决，那么只需在最后一步在输出取反就可以得到其反问题（反问题也即所有输入上输出都相反的问题）的算法。然而，我们不能用同样的方式说明$\text{NPSPACE}=\overline{\text{NPSPACE}}$，因为非确定性图灵机只需在某个状态判定1就会输出1，其反问题要求其所有状态都判定0，不能说明其空间复杂性。然而，有Savitch定理作为桥梁，我们有：$\text{NPSPACE}=\text{PSPACE}=\overline{\text{PSPACE}}=\overline{\text{NPSPACE}}$。

对于任何复杂性类$T$，都有$\overline{T}\subseteq T\iff T\subseteq \overline{T}\iff T=\overline{T}$。这只是关于问题的补和复杂性类的补的概念的展开罢了。$\forall L\in\overline{T}$，$L\in T$，等价于$\forall L\in T,\overline{L}\in T$，等价于$\forall L\in T,L\in \overline{T}$。

事实上也成立$\text{NL}=\overline{\text{NL}}$，但是在证明时Savitch定理不再适用。我们必须回到该类中的完全问题这一层面来证明。由$\texttt{Reachability}$是NL-complete的，$\forall A\in \text{NL},A\leq_L \texttt{Reachability}$。由隐式对数空间归约的定义，$\forall A\in\text{NL},\overline{A}\leq_L\overline{\texttt{Reachability}}$。等价于，$\forall A\in\overline{\text{NL}},A\leq_L\overline{\texttt{Reachability}}$。而$\overline{\texttt{Reachability}}\in\overline{\text{NL}}$，可见$\overline{\texttt{Reachability}}$是$\overline{\text{NL}}$-complete的。于是关键在于，如果我们能够证明$\overline{\texttt{Reachability}}\in\text{NL}$，那么$\overline{\text{NL}}$中的问题都可以归约到$\text{NL}$，因此$\overline{\text{NL}}\subseteq \text{NL}$，所以$\overline{\text{NL}}=\text{NL}$。$\overline{\texttt{Reachability}}\in\text{NL}$的证明称为Szelepcsenyi-Immerman定理。Pf. 我们已经知道我们可以用非确定性图灵机在对数空间判定一个点到另一个点是否存在路径， 现在我们想构造一个非确定性算法，在对数空间判定一个点到另一个是否不可能存在路径。这个构造非常巧妙。设起点为$s$，终点为$t$，令$C_i$表示$s$出发$i$步内能到达的节点集合，设$c_i=|C_i|$表示集合的大小。我们只需判定是否成立$t\not\in C_{n-1}$即可。首先，容易计算出$c_1$，只需访问$s$的邻居。下面我们证明，可以用$c_i$的信息计算出$c_{i+1}$，如果这样我们只需在读写带上记录上一轮的$c_i$就可以最终计算出$c_n$（一个$c_i$是对数空间的）。方法是， 假设$c_i$已知，枚举图上的所有$n$个节点$v$，非确定性允许我们同时进入两个叠加的状态：猜测$v\in C_{i}$或猜测$v\not\in C_{i}$。如果对于$v$我们猜测了$v\in C_{i}$，那么我们可以调用可达性判定的非确定性图灵机判定此猜测是否成立，如果不成立则终止这一分支；如果我们猜测了$v\not\in C_{i}$，而这一猜测实际是错的，那么当$n$个节点的猜测全都结束后，我们可以统计算法所猜测的$C_{i}$的大小（这一计数器是对数空间的）。由于目前分支没有终止，算法所作的猜测一定不超过实际的$C_{i}$大小（因为猜属于的都经过验证了），因此我们只需将结果与$c_i$比较，如果不相等则终止此分支。最终，一定存在且仅存在一个分支，这里算法恰好完全猜测对了$C_i$的构成，在这个分支下，我们自然能够对数空间统计出$C_{i+1}$的大小（只需考察中$C_i$中存在的节点以及由$C_i$中的节点直接相连的节点），也即得到了$c_{i+1}$。最终，我们能够正确得到$c_{n-1}$，并且能够再次以同样的方法得到$C_{n-1}$的构成，也就能够判定是否成立$t\not\in C_{n-1}$。Qed.

证明的相对化(The Relativization of Proofs)

当我们要证明两类问题$A$和$B$并不相等时，如果关于$A\neq B$的证明可以对于任意oracle $O$被一模一样的套用而用来证明$A^O\neq B^O$，那么就称这是一个可相对化的(relativize)证明。

一个重要的问题是，如果存在$P\neq NP$的证明，那么这个证明是否有可能是可相对化的呢？Baker-Gill-Solovay定理用对角线方法证明了存在问题$B$使得$\text{P}^B\neq \text{NP}^B$。这意味着，$P\neq NP$的证明一定是不可相对化的。

事实上，复杂性理论中很多深刻的结果的证明都是不可相对化的（例如加速定理的证明）。Baker-Gill-Solovay定理的证明本身也是不可相对化的。

显然是存在问题$A$使得$P^A=NP^A$的。取$\text{PSPACE}$-complete的量化布尔公式问题QBF作为oracle $A$，在这个oracle下的所有确定性图灵机多项式可判定的问题$\text{P}^{\text{QBF}}$一定等于这个oracle下的所有非确定性图灵机多项式可判定的问题$\text{NP}^{\text{QBF}}$。原因是，$\text{P}^{\text{PSPACE}}\subseteq \text{NP}^{\text{PSPACE}}$，而显然$\text{P}^\text{PSPACE}=\text{PSPACE}$，$\text{NP}^\text{PSPACE}=\text{PSPACE}$，所以$\text{P}^{\text{PSPACE}}=\text{NP}^{\text{PSPACE}}$。而由于所有$\text{PSPACE}$问题都可以归约为$\text{QBF}$，所以有$\text{P}^{\text{QBF}}=\text{NP}^{\text{QBF}}$。