Mahaney's Theorem

让武器让位于长袍吧。

这个定义了什么是 “稀疏” 的语言。直观地说，就是$L$ 中长度为$n$ 的字符串数量至多是$n$ 的多项式级别。

考虑如下定理：

在证明之前，我们先考虑这个定理说明了什么，它实际上刻画了$NP$-hard 语言的 “难度”。有人曾猜测：

对于一个$NP$-hard 的语言，是否存在一个多项式算法，使得对 “大多数” 情况都是正确的？

Mahaney’s Theorem 就否定了这种猜测。它说明，$NP$-hard 的语言确实是难的，并且不存在 “大多数情况正确” 的可能。

---

下面我们证明这个定理。反设存在一个这样的语言$L$，那么我们证明$SAT\in P$，那么就可得出$P=NP$ 与假设矛盾。

因为$L\in NP$-hard，故存在多项式规约$R$，使得：

$$SAT\leq_m^p L$$

类似 Ladner’s Theorem，既然规约是多项式时间的，故规约的结果长度最多也是多项式级的：

$$\forall \phi\in\{0,1\}^n, |R(\phi)|\leq|\phi|^r$$

当然，上式并不完全严谨，右侧应为$O(|\phi|^r)$，但多项式意义下不影响证明的思想。

我们考虑 “规约” 的含义，有：

$$\begin{cases} \phi\in SAT\Leftrightarrow R(\phi)\in L\\ \phi\notin SAT\Leftrightarrow R(\phi)\notin L \end{cases}$$

对于一个输入$\phi\in \{0,1\}^n$，那么有$R(\phi)\in\{0,1\}^{n^ r}$。

$R$ 是一个从长为$n$ 的字符串集，向长为$n^r$ 的字符串集的一个多项式函数。而因为假设$L$ 是 sparse 的：

$$|L\cap \{0,1\}^{n^r}|\leq (n^r)^c=n^{rc}$$

所以我们知道$L$ 中长度为$n^r$ 的字符串数量是关于$n$ 的多项式级别。即$|L|\leq n^{rc}$。（同理为了方便不适用大$O$ 符号，以及我们只考虑了长度为$n^r$ 的字符串，因为我们是在$R$ 的像集中讨论的）

那么这个规约配合上 sparse 就会有很好的性质。记$T=n^{rc}+1$，那么对多项式个的一组输入：

$$\phi_0,\phi_1,...,\phi_T$$

和它们规约的结果：

$$R(\phi_0),R(\phi_1),...,R(\phi_T)$$

下面两种情况必然有一个成立：

• $R(\phi_i)$ 各不相同。那么根据抽屉原理，存在一个$R(\phi_i)\notin L$。
• 存在$R(\phi_i)=R(\phi_j)$。此时，$\phi_i$ 和$\phi_j$ 要么同时可满足，要么都不可满足。

有了上述性质，我们可以开始着手多项式时间解决$SAT$ 问题。

我们递归地去解决，对于一个输入$\phi\in\{0,1\}^n$，我们要判定它是否可满足，可以先把第一个变量赋值为 0 和 1，得到新的$SAT$ 问题$\phi_{x_1=0},\phi_{x_1=1}$ 然后如果有一个分支是可满足的，就输出 1，否则为 0。

$$\phi\rightarrow\begin{cases} \phi_{x_1=0}\rightarrow \begin{cases} \phi_{x_1=0,x_2=0}\rightarrow\begin{cases}...\\...\end{cases}\\ \phi_{x_1=0,x_2=1}\rightarrow\begin{cases}...\\...\end{cases} \end{cases} \\ \phi_{x_1=1}\rightarrow \begin{cases} \phi_{x_1=1,x_2=0}\rightarrow\begin{cases}...\\...\end{cases}\\ \phi_{x_1=1,x_2=1}\rightarrow\begin{cases}...\\...\end{cases} \end{cases} \end{cases}$$

显然这是一个完全二叉树，就是在枚举，是指数级别的复杂度。

但是我们可以证明，当分支过多时，我们可以用之前的性质在多项式时间内进行剪枝，保证分支数量$\leq T$。

譬如此时有分支$\phi_0,...,\phi_T$，数量大于$T$ 了。此时我们：

• 构造$\psi_1=\phi_0\vee\phi_1,...,\psi_T=\phi_0\vee\phi_T$。
• 计算规约$R(\psi_1),...,R(\psi_T)$。可以判断会有两种情况：
  • $R(\psi_1),...,R(\psi_T)$ 互不相同。此时我们知道存在$R(\psi_i)\notin L$，即$\psi_i=\phi_0\vee\phi_i$ 不可满足。尽管我们不知道是哪个$i$，但是显然共同点是$\phi_0$ 都不可满足。故我们剔除$\phi_0$。
  • 若存在$R(\psi_i)=R(\psi_j)$。那同样显然，我们把$\phi_i$ 和$\phi_j$ 剔除一个即可。因为它们有相同的可满足性。

综上，若共有$n$ 个变量，输入串长度也是$n$ 级别，而且分支数量始终保持在$T=n^{rc}+1$ 级别（关于$n$ 多项式级别），故得到了一个多项式求解算法，矛盾。故证毕