博文
k-Sat归约到3sat求解只会得到部分解
|||
k-Sat归约到3sat求解只会得到部分解
姜咏江
当k>3时，k-SAT归约到3-SAT的公式:
k-CNF=(x1+x2+y1) (y’1+x3+y2) (y’2+x3+y3)…(xk-1+xk+y’k-3)
用01表格式表达的5-CNF如表1所示，最上面一行是变量取值。
表1 5-CNF
0 | 1 | 1 | 0 | * |
x1 | x2 | x3 | x4 | x5 |
0 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 0 | 1 |
1 | 1 | 0 | 1 | 1 |
1 | 0 | 1 | 1 | 0 |
1 | 0 | 1 | 0 | 1 |
将表1 的5-CNF归约到3-CNF如表2所示。
表2 归约成3-CNF
|
|
|
|
|
|
|
x1 | x2 | x3 | x4 | x5 | y1 | y2 |
0 | 0 |
|
|
| 1 |
|
|
| 0 |
|
| 0 | 1 |
|
|
| 0 | 0 |
| 0 |
1 | 0 |
|
|
| 1 |
|
|
| 0 |
|
| 0 | 1 |
|
|
| 0 | 1 |
| 0 |
1 | 1 |
|
|
| 1 |
|
|
| 0 |
|
| 0 | 1 |
|
|
| 1 | 1 |
| 0 |
1 | 0 |
|
|
| 1 |
|
|
| 1 |
|
| 0 | 1 |
|
|
| 1 | 0 |
| 0 |
1 | 0 |
|
|
| 1 |
|
|
| 1 |
|
| 0 | 1 |
|
|
| 0 | 1 |
| 0 |
表2 出现了重复子句，按照子句块排列，并消除重复子句表示，化简得到表3。
将表3的3-CNF按照子句消去法进行求解。
（1）有4同值变量y2=0，则可消去后面的4行。
（2）若选取y1=1，则有x3不能够取值，造成3-CNF=1无解；所以取值y1=0，选取相应子句。
（3）取y1=0值后，还剩3个子句，且有一个变量的值已经确定，故必选x1=1，x2=0才能够将全部子句消去。
这样我们在3-CNF=1得到一组解x1 x2 x3 x4 x5=10***，“*”表示是0或1，y1=0， y2=0不涉及5-CNF=1求解。
表3 3-CNF化简
1 | 0 | * | * | * | 0 | 0 |
x1 | x2 | x3 | x4 | x5 | y1 | y2 |
0 | 0 |
|
|
| 1 |
|
1 | 0 |
|
|
| 1 |
|
1 | 1 |
|
|
| 1 |
|
|
| 0 |
|
| 0 | 1 |
|
| 1 |
|
| 0 | 1 |
|
|
| 0 | 0 |
| 0 |
|
|
| 1 | 1 |
| 0 |
|
|
| 1 | 0 |
| 0 |
|
|
| 0 | 1 |
| 0 |
对于这个3-CNF=1求解的每一步都是唯一解，所以不可能再有其它的解。
小结：由表意1可见x1 x2 x3 x4 x5=0110*也是这个5-SAT例题的解。自然会想到A归约到B后，通过B只能够求出A的部分解。
2015-12-25
https://blog.sciencenet.cn/blog-340399-945744.html
上一篇：我以往博客中的附图都没有了，能恢复吗？
下一篇：柳渝你还认为子句消去法证明的是P=P吗？
