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

博文

k=n时k-SAT能快速求解吗?答田文洪老师

已有 3677 次阅读 2016-6-29 12:57 |个人分类:k-SAT求解|系统分类:科研笔记| 多项式时间, 子句标志消去法, K-SAT

k=nk-SAT能快速求解吗?

答田文洪老师

 [7]田文洪  2016-6-28 21:45 

姜老师,一种情况就是如同SAT问题(可把3-SAT看作其特殊组合形式),当CNF输入项是2^k个不同项时,你所建议的方法的计算复杂度。此种情况可能是SA丅问题的最坏或最难情况,应该说明一下。

博主回复(2016-6-28 21:59)田老师,子句标志消去法基础在于反子句的概念。SAT是1到k个变量的子句都可能存在,都有反子句。只要n位二进制数可以由无反子句的子句或不在SAT中的子句构成,那么这个数就一定是SAT的解。

上面是我与田老师的交流(见http://blog.sciencenet.cn/blog-340399-987007.html)。我的回复不会使田老师满意吧?也许答非所问。遵照田老师的建议,我需要很好地解答这方面的问题,这样能够一起更好地讨论。

1.  k=n 子句就是标志

若k=n,那么k-SAT中每个子句就是它的标志。因而只要看n位二进制数有哪些数不在k-SAT当中,取其反码则为解。特别是当子句数为2n个时,可以直接判定无解。这种情况应该说最简单,而不是最复杂。虽然k=n时最多可有2n个子句,但我们查找的是不在0~2n-1中的数,这个过程的算法时间复杂度为O(x),x是一个变量。

2.  怎样理解SAT

有n个变量的SAT,子句可以从1阶到n阶,因而各阶的子句总数会远远超过2n,但依子句消去法可知,低阶子句消去的同时,包含低阶子句的高阶子句也同时被削去了。由于低阶子句数总是高阶子句的组成部分,如果任何一低阶子句存在完全子句块,SAT都不会有解。不然从低向高阶施行子句标志消去的过程,剩下的子句标志都与剩下的n阶子句数有关。由1可知,其操作过程同k=n时的复杂度相同。

我们还是举例说明吧。

例如,在下面的SAT中有2阶和3阶子句。当我们操作低阶子句消去子句标志时,高阶子句如果包含低阶子句,那么高阶子句的子句标志也同时被消去了,这样剩下的子句标志一定都是被消去子句的反子句或SAT中没有的子句构成的。于是知剩下的这些n位数的反码,一定是SAT的解。

 

x4

x3

x2

x1

x0

 

NO

 

x4

x3

x2

x1

x0

 

1

0

 

 

 

 

0

 

0

0

0

0

0

 

0

0

 

 

 

 

1

 

0

0

0

0

1

 

0

0

0

 

 

 

2

 

0

0

0

1

0

 

1

0

0

 

 

 

3

 

0

0

0

1

1

 

1

0

1

 

 

 

4

 

0

0

1

0

0

 

1

1

1

 

 

 

5

 

0

0

1

0

1

 

0

 

0

1

 

 

6

 

0

0

1

1

0

 

1

 

1

0

 

 

7

 

0

0

1

1

1

 

1

1

 

 

1

 

8

 

0

1

0

0

0

 

0

0

 

 

0

 

9

 

0

1

0

0

1

 

 

1

0

1

 

 

10

 

0

1

0

1

0

 

 

1

1

0

 

 

11

 

0

1

0

1

1

 

 

0

1

1

 

 

12

 

0

1

1

0

0

 

 

1

1

1

 

 

13

 

0

1

1

0

1

 

 

0

0

0

 

 

14

 

0

1

1

1

0

 

 

 

0

1

0

 

15

 

0

1

1

1

1

 

 

 

1

0

0

 

16

 

1

0

0

0

0

 

 

 

1

1

0

 

17

 

1

0

0

0

1

 

 

 

0

0

1

 

18

 

1

0

0

1

0

 

 

 

 

 

 

 

19

 

1

0

0

1

1

 

 

 

 

 

 

 

20

 

1

0

1

0

0

 

 

 

 

 

 

 

21

 

1

0

1

0

1

AS.8'

1

0

1

1

1

 

22

 

1

0

1

1

0

AS.24'

0

0

1

1

1

 

23

 

1

0

1

1

1

 

 

 

 

 

 

 

24

 

1

1

0

0

0

 

 

 

 

 

 

 

25

 

1

1

0

0

1

 

 

 

 

 

 

 

26

 

1

1

0

1

0

 

 

 

 

 

 

 

27

 

1

1

0

1

1

 

 

 

 

 

 

 

28

 

1

1

1

0

0

 

 

 

 

 

 

 

29

 

1

1

1

0

1

 

 

 

 

 

 

 

30

 

1

1

1

1

0

 

 

 

 

 

 

 

31

 

1

1

1

1

1

 

是否正确,还请多多指正。 

姜咏江

2016-6-29

 



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

上一篇:为k-SAT问题彻底解决欢呼,感谢杜立智的精彩评论
下一篇:3-SAT问题中如何选择算法操作对象?
收藏 IP: 120.52.24.*| 热度|

0

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

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

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

GMT+8, 2024-3-29 17:00

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部