子句包含消去法多项式时间证明

姜咏江

子句包含消去法是在3-SAT的解空间（2ⁿ个n位二进制数）中，逐一消去那些包含子句的可能解(n位数)的过程。设3-SAT子句有m个，那么全部子句处理完成，计算次数为

(2ⁿ-2^n-3)+ (2ⁿ-2^n-3-2^n-3)+ (2ⁿ-2^n-3-2^n-3-2^n-3)+…+(2ⁿ-2^n-3-2^n-3-2^n-3-…-2^n-3)

=(2ⁿ-2^n-3) +(2ⁿ-2*2^n-3) + (2ⁿ-3*2^n-3)+…+ (2ⁿ-(m-1)2^n-3) + (2ⁿ-m2^n-3)

=m2ⁿ –(1+2+3+…+m) 2^n-3

= m2ⁿ –m(m+1) 2^n-4

= m2ⁿ (1-(m+1) 2^-4).                            

这是一个关于n的指数时间复杂度，是关于2ⁿ的多项式时间复杂度。

仿量子计算机一次可以处理2ⁿ个n位二进制数，因而令N=2ⁿ，则子句包含消去法是一个关于m的多项式

m(1-(m+1) 2^-4)时间算法。

如今，只有并行计算的仿量子计算机可以这样快速计算，虽说量子计算机也可以如此计算，但量子计算机尚在襁褓之中，选择仿量子计算机是明智之举。