Ladner定理

Ladner定理：若P≠NPP
eq NPP=NP，那么NPNPNP中必然存在不是NP−CompleteNP-CompleteNP−Complete的语言，即∃A∈NP,SAT̸≤mPAexist Ain NP,SAT
otle^P_m A∃A∈NP,SAT≤mPA，其中SATSATSAT表示可满足的合取表达式，̸≤mP
otle^P_m≤mP表示多项式时间多一归约（Karp归约）。事实上，可以证明一个更强的结论，∃A∈NP,SAT̸≤TPAexist Ain NP,SAT
otle^P_T A∃A∈NP,SAT≤TPA，其中̸≤TP
otle^P_T≤TP表示多项式时间图灵归约（Cook归约）。
证明思路：对SATSATSAT语言进行某种形式的“选取”，然后通过惰性对角线方法（delayed diagonalization）来构造选取方法，即并不是像证明停机定理那样直接通过模拟取反，而是分为n个阶段逐步构造一个反例，从而使得枚举出来的图灵机均对应一个反例，完成对角线形式的构造。
定理实际上可以表述成三个部分：（1）A∈NPAin NPA∈NP；(2)A∉PA
otin PA∈P；(3)SAT̸≤TPASAT
otle^P_T ASAT≤TPA。若以MiM_iMi代表用整数iii的位串表示确定性多项式时间图灵机，以以NiN_iNi代表用整数iii的位串表示带某个Oracle的确定性多项式时间图灵机，则定理的三个部分可以分别改写为：（1）A≤mPSATAle^P_m SATA≤mPSAT；（2）∀i≥1，A≠L(Mi)forall ige 1，A
e L(M_i)∀i≥1，A=L(Mi)；（3）∀i≥1，SAT≠L(Ni,A)forall ige 1，SAT
e L(N_i,A)∀i≥1，SAT=L(Ni,A)，其中L(Mi)L(M_i)L(Mi)代表图灵机MiM_iMi所判定的语言，L(Ni,A)L(N_i,A)L(Ni,A)代表图灵机NiN_iNi以语言AAA为Oracle时所判定的语言。
按照前面所述，我们可以假设A=SAT∩SA=SATcap SA=SAT∩S，其中S∈PSin PS∈P就隐含了我们对SATSATSAT语言的选取方法，接下来逐一证明这三个部分。
证明：（1）对于x∈{0,1}∗xin {0,1}^*x∈{0,1}∗，可以直接定义一个归约函数