|||
子句包含消去法多项式时间证明
姜咏江
子句包含消去法是在3-SAT的解空间(2n个n位二进制数)中,逐一消去那些包含子句的可能解(n位数)的过程。设3-SAT子句有m个,那么全部子句处理完成,计算次数为
(2n-2n-3)+ (2n-2n-3-2n-3)+ (2n-2n-3-2n-3-2n-3)+…+(2n-2n-3-2n-3-2n-3-…-2n-3)
=(2n-2n-3) +(2n-2*2n-3) + (2n-3*2n-3)+…+ (2n-(m-1)2n-3) + (2n-m2n-3)
=m2n –(1+2+3+…+m) 2n-3
= m2n –m(m+1) 2n-4
= m2n (1-(m+1) 2-4).
这是一个关于n的指数时间复杂度,是关于2n的多项式时间复杂度。
仿量子计算机一次可以处理2n个n位二进制数,因而令N=2n,则子句包含消去法是一个关于m的多项式
m(1-(m+1) 2-4)时间算法。
如今,只有并行计算的仿量子计算机可以这样快速计算,虽说量子计算机也可以如此计算,但量子计算机尚在襁褓之中,选择仿量子计算机是明智之举。
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-11-6 17:36
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社