博文
k=n时k-SAT能快速求解吗？答田文洪老师
|||
k=n时k-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://blog.sciencenet.cn/blog-340399-987475.html
上一篇：为k-SAT问题彻底解决欢呼，感谢杜立智的精彩评论
下一篇：3-SAT问题中如何选择算法操作对象？
