CMP设计分享 http://blog.sciencenet.cn/u/accsys 没有逆向思维就没有科技原创。 不自信是科技创新的大敌。

博文

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

已有 1846 次阅读 2019-11-26 05:40 |个人分类:仿量子计算机|系统分类:科研笔记| 子句包含消去法, 3-SAT, 多项式时间

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

姜咏江

子句包含消去法是在3-SAT的解空间(2nn位二进制数)中,逐一消去那些包含子句的可能解(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的多项式时间复杂度。

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

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

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




https://wap.sciencenet.cn/blog-340399-1207575.html

上一篇:数字密码锁的快速破解
下一篇:数据密码软锁的应用
收藏 IP: 116.243.238.*| 热度|

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-11-6 17:36

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部