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

博文

基于3SAT问题说明子句消去法的多项式时间复杂度

已有 4101 次阅读 2016-12-8 08:44 |个人分类:3SAT解法|系统分类:科研笔记| 子句消去法, 多项式时间复杂度, 3SAT问题

基于3SAT问题说明子句消去法的多项式时间复杂度

姜咏江

为让大家能理解子句消去法的多项式时间复杂度特性,本文就以3SAT问题来简单说明。三个变量的子句在施行子句消去法的过程中,也会出现一个变量或两个变量的子句。因而3SAT问题实际就是最高阶是3SAT问题。

算法

1子句消去法先查找子句块变量无解和唯一解。有变量无解计算结束,不然连续消去唯一解剩余子句块,出现变量无解结束计算,出现剩余子句块全多解时,选择另外子句块变量唯一解操作。

2没有了子句块变量唯一解,就去找关联变量(属于不同子句块的变量)的可选解。这一过程中需要对变量0值和1值分别施行子句消去测试可选解的数量。如果变量测试有唯一可选解,就按照(1)的方法计算,不然标记这个变量有2个可选解,然后选择另外的关联变量测试。

3剩余SAT全部变量都有2个可选解。此时计算最为简单,只要任意设定一个变量的值后,施行子句消去法,最终就可以得到SAT的满足解。

复杂度

假设3SAT的每个子句块都没有唯一解变量,而且每一个变量都是关联变量,并且n个变量都需要判定可选解的数量。这应该是3SAT求满足解时间复杂度最坏的情况。

A.                  查找无解和唯一解。由于3SAT的子句块最多有Cn3个,每个子句块最多有8个子句。有8个子句的子句块存在,3SAT无解。子句块中一个变量只有4个相同值就有唯一解。所以最坏的情况下,这些特点都不会出现。这只要对每个子句块变量进行01的统计就可以做到。因而最多要统计8Cn3次。可见时间复杂度为不超过O(n3)

B.                   确定变量可选解。假设测试变量是所有子句块的变量,那么设定值为1都要对每个子句块确定一次无解或无变量唯一解。检查的子句块仍然不会超过Cn3个,最多要统计8Cn3次。故这步算法的时间复杂度也不超过2nO(n3),即为O(n4)

C.                   确定了每个变量都有2个可选解消去子句。由于有定理保证,所以按照子句消去法设定各变量的值,消去子句的时间复杂度显然是不超过O(n)

 

从这3步操作来看,不过是有限个多项式时间的和而已,故可知3SAT问题子句消去法求解的时间复杂度最坏是O(n4)

 

2016-12-8

 



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

上一篇:子句消去法求解SAT问题思想方法如此简单
下一篇:包括批评我的那些关心子句消去法的人都是我珍贵的朋友
收藏 IP: 120.52.94.*| 热度|

0

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

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

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

GMT+8, 2024-11-9 15:11

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部