让武器让位于长袍吧。

Definition: Say a language LL is sparse if:

nN,L{0,1}nO(nc)\forall n\in\mathbb{N},|L\cap\{0,1\}^n|\leq O(n^c)

for some constant cc

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

考虑如下定理:

Mahaney’s Theorem: Assume PNPP\neq NP, then for all NPNP-hard language LL, LL is NOT sparse.

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

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

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


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

因为LNPL\in NP-hard,故存在多项式规约RR,使得:

SATmpLSAT\leq_m^p L

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

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

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

我们考虑 “规约” 的含义,有:

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

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

RR 是一个从长为nn 的字符串集,向长为nrn^r 的字符串集的一个多项式函数。而因为假设LL 是 sparse 的:

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

所以我们知道LL 中长度为nrn^r 的字符串数量是关于nn 的多项式级别。即Lnrc|L|\leq n^{rc}。(同理为了方便不适用大OO 符号,以及我们只考虑了长度为nrn^r 的字符串,因为我们是在RR 的像集中讨论的)

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

ϕ0,ϕ1,...,ϕT\phi_0,\phi_1,...,\phi_T

和它们规约的结果:

R(ϕ0),R(ϕ1),...,R(ϕT)R(\phi_0),R(\phi_1),...,R(\phi_T)

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

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

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

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

ϕ{ϕx1=0{ϕx1=0,x2=0{......ϕx1=0,x2=1{......ϕx1=1{ϕx1=1,x2=0{......ϕx1=1,x2=1{......\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}

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

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

譬如此时有分支ϕ0,...,ϕT\phi_0,...,\phi_T,数量大于TT 了。此时我们:

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

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