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

Ladner’s Theorem: Assume that PNPP\neq NP, then there exists a language LPL\notin P and LL is not NPNP-complete.

我们先考虑一下这个定理说明了什么。首先,PPNPNP-complete 都是NPNP 问题的子集。首先考虑下面两幅图:

1

P=NPP=NP,则如右图P=NP=NPP=NP=NP-complete。但如果PNPP\neq NP,那么 Ladner’s Theorem 就说明,PPNPNP-complete 间是有” 空隙 “的。并不是所有NPNP 问题要么是PP,要么是NPNP-complete 的。


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

Exponential Time Hypothesis(unproven): 3-SAT problem cannot be solved in subexponential time, i.e.

δ>0,3SATDTIME(2δn)\exists \delta>0,3SAT\notin DTIME(2^{\delta n})

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

我们构造如下一个 language:

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

  • 首先,LNPL\in NP。证明如下:

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

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

    LNPL\in NP

  • 其次,LPL\notin P。证明如下:

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

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

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

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

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

    矛盾。故LPL\notin P

  • 最后,LNPL\notin NP-complete。实际上,它不够难以至于不是NPNP-hard 的。证明如下:

    反设LNPL\in NP-hard,因为3SATNP3SAT\in NP-hard,故有3SATmpL3SAT\leq_m^p L

    我们先构造一个图灵机MM,它能够在时间O(log2NNlogN)O(log^2N\cdot N^{logN}) 的时间内判定LL

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

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

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

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

LNP,LP,LNPL\in NP,L \notin P,L\notin NP-complete。证毕。