Ladner's Theorem

蔑视对方的人，眼睛的情态最为有趣。他们的眼神里，有着对反驳的胆怯与警戒，有时候，还藏着一种 “你敢反驳我便应战” 的好战光芒。当他们无意识地蔑视我时，混杂着优越感的迷醉快感会形成一种液体，浸润眼球，有时甚至形成一片水膜。

我们先考虑一下这个定理说明了什么。首先，$P$ 和$NP$-complete 都是$NP$ 问题的子集。首先考虑下面两幅图：

若$P=NP$，则如右图$P=NP=NP$-complete。但如果$P\neq NP$，那么 Ladner’s Theorem 就说明，$P$ 和$NP$-complete 间是有” 空隙 “的。并不是所有$NP$ 问题要么是$P$，要么是$NP$-complete 的。

下面我们证明一个较弱的定理形式，也就是引入了 Exponential Time Hypothesis (E.T.H) 后，去证明 Ladner’s Theorem。

当然因为我们不知道$P=?NP$，也不知道 3SAT 问题是否可以多项式时间解决。所以这个 E.T.H 实际上也是一个假设。下面借助它我们来证明 Ladner’s Theorem。

我们构造如下一个 language：

$$L=\{\langle x,1^{2^{\sqrt{|x|}}}\rangle\;|\;x\in 3SAT\}$$

• 首先，$L\in NP$。证明如下：

  我们构造一个用于验证的图灵机$V(y,z)$：

  1. 对于输入$y$，验证$y$ 的形式是否为$y=\langle x,1^{2^{\sqrt{|x|}}}\rangle$，如果不是，则拒绝。这一步需要时间为$O(2^{c\sqrt{|x|}})=O(|y|^c)$。
  2. 然后令$z$ 是满足$x$ 编码的 3SAT 问题的一个解，可以在多项式时间内验证$z$ 是否使得$x$ 可被满足。

  故$L\in NP$。

• 其次，$L\notin P$。证明如下：

  反设存在一个图灵机$M$ 可以在$O(N^c)$ 时间内判定$L$。注意，$N=|y|=O(2^{\sqrt{|x|}})$。

  那么我们可以构造一个时间复杂度低的图灵机$M'$ 去判定 3SAT，从而违反 E.T.H。

  1. 对于输入$x$，首先 pad 成形式$\langle x,1^{2^{\sqrt{|x|}}}\rangle$。 这一步需要需要时间$O(2^{\sqrt{|x|}})$ 。
  2. 运行$M$, 即在$O(2^{c\sqrt{|x|}})$ 的时间内判定了 3SAT。

  上述图灵机所需时间为$2^{O(\sqrt{|x|})}$。此时违反了 E.T.H。很显然，$2^{O(\sqrt{|x|})}<<2^{\delta n}$，故：

  $$\forall \delta>0,3SAT\in DTIME(2^{O(\sqrt{|x|})})\subseteq DTIME(2^{\delta n})$$

  矛盾。故$L\notin P$。

• 最后，$L\notin NP$-complete。实际上，它不够难以至于不是$NP$-hard 的。证明如下：

  反设$L\in NP$-hard，因为$3SAT\in NP$-hard，故有$3SAT\leq_m^p L$。

  我们先构造一个图灵机$M$，它能够在时间$O(log^2N\cdot N^{logN})$ 的时间内判定$L$：

  1. 对于输入$y$，首先检查它的形式是否符合$y=\langle x,1^{2^{\sqrt{|x|}}}\rangle$。这一步复杂度为$O(2^{c\sqrt{|x|}})=O(N)$。
  2. 然后提取出$x$，它是一个 3SAT 问题，我们用枚举法去解决它。这一步复杂度为$O(|x|\cdot 2^{|x|})=O(log^2N\cdot 2^{log^2N})=O(log^2N\cdot N^{logN})$。

  此时，3SAT 问题也可以复杂度很低地解决了。

  因为$3SAT\leq_m^p L$，故对于一个输入$x$，我们首先执行多项式时间规约得到一个输出$y$，而且$|y|=O(|x|^c)$。注意这一步需要考虑一下，我们其实认为：多项式规约出的$y$ 长度一定是输入$x$ 的长度的多项式级别。为什么？因为多项式规约也只能执行多项式步。当然这个看起来很奇怪，因为我们总想着$y=\langle x,1^{2^{\sqrt{|x|}}}\rangle$，但实际上这样的规约并不存在，所以$y$ 并不是那样的形式，只需要知道有这么个$y$ 即可。

  规约后，就可以用上述图灵机去判定 3SAT 了，复杂度为$O(log^2|y|\cdot |y|^{log|y|})=O(log^2|x|\cdot |x|^{clog|x|})<<O(2^{\delta n})$。故违反了 E.T.H。

故$L\in NP,L \notin P,L\notin NP$-complete。证毕。