博文
详解3SAT归约到子集和问题的方法
|||
详解3SAT归约到子集和问题的方法
姜咏江
《算法导论》一书对3SAT规约到子集和论述不够，特作如下详细解释。
1. 确认表示与01表示
先给出一个3-CNF=(x'1+ x'2+ x'3)( x'1+ x'2+ x3)(x1+ x2+ x3)( x2+ x3+ x'4)( x2+ x'3+ x'4)的例子。表1是这个3-CNF的确认表示法，表2是它的01表示法。表1有底纹与无底纹的选择，分别表示选择x1=1，x2=1，x3=1，x4=1和x1=0，x2=0，x3=0，x4=0，这两种选值都不是3-CNF=1的解。
不难看出，3-CNF=1求解的问题，在表1中变成了sum是否没有0数据位的问题；而在表2中就变成了是否有剩余子句的问题。
表1 3-CNF确认表示法（无解） 表2 3-CNF01表示法
x1 | x'1 | x2 | x'2 | x3 | x'3 | x4 | x'4 | sum |
| x1 | x2 | x3 | x4 | |
| 1 |
| 1 |
| 1 |
|
| 0 | 3 |
| 0 | 0 | 0 |
|
| 1 |
| 1 | 1 |
|
|
| 1 | 2 |
| 0 | 0 | 1 |
|
1 |
| 1 |
| 1 |
|
|
| 3 | 0 |
| 1 | 1 | 1 |
|
|
| 1 |
| 1 |
|
| 1 | 2 | 1 |
|
| 1 | 1 | 0 |
|
| 1 |
|
| 1 |
| 1 | 1 | 2 |
|
| 1 | 0 | 0 |
例如选择x1=1，x2=0，x3=0，x4=0或x1=0，x2=1，x3=1，x4=1，那么sum没有为0数位，3-CNF=1都有解。
表3 3-CNF确认表示法（有解） 表4 3-CNF01表示法
x1 | x'1 | x2 | x'2 | x3 | x'3 | x4 | x'4 | sum |
| x1 | x2 | x3 | x4 | |
| 1 |
| 1 |
| 1 |
|
| 2 | 1 |
| 0 | 0 | 0 |
|
| 1 |
| 1 | 1 |
|
|
| 1 | 2 |
| 0 | 0 | 1 |
|
1 |
| 1 |
| 1 |
|
|
| 1 | 2 |
| 1 | 1 | 1 |
|
|
| 1 |
| 1 |
|
| 1 | 1 | 2 |
|
| 1 | 1 | 0 |
|
| 1 |
|
| 1 |
| 1 | 2 | 1 |
|
| 1 | 0 | 0 |
依据子句消去法对合取范式3SAT求解中，只要出现2选值变量的4种不同值，就会出现无解情况（参阅：http://blog.sciencenet.cn/blog-340399-928224.html）。因此只要这里选x1=1和x4=1，就会出现关联段无解的情况，即不论x2、x3为何值，3-CNF=1都无解。这方面从表1可得验证，无论如何sum总有0值出现。
容易知道3-CNF的变量值确认表中每个子句的标志和sum=3，若其中正变量取值数为s，则其反变量必取3-s个。
引理：n元变量k-CNF确认表示法中选择n列向量求和，不出现为0分量，则得k-CNF=1有解，反之无解。
证明：因为确认表示法向量的每个分量值为1代表01表示法的选中0或1的确认，它们之间是一一对应的关系。故01表示法的子句变量值选中，必在确认表示法有1存在，反之亦然。由此可知引理成立。
2. 3SAT归约成子集和
由k-CNF的确认表示法很容易转换成特殊的子集和。由表1可见，将每列的空格认为是0，那么那么求和就变成了子集和问题。为了不出现相同的数，增加4行（见表5），为了能够求出和的低4位为固定数3+1，选择松弛变量｛1，2｝。
表5 特殊的子集和问题（下面是高位）
x1 | x'1 | x2 | x'2 | x3 | x'3 | x4 | x'4 | s1 | s'1 | s2 | s'2 | s3 | s'3 | s4 | s'4 | S5 | s'5 | sum |
| 1 |
| 1 |
| 1 |
|
| 1 | 2 |
|
|
|
|
|
|
|
| 4 |
| 1 |
| 1 | 1 |
|
|
|
|
| 1 | 2 |
|
|
|
|
|
| 4 |
1 |
| 1 |
| 1 |
|
|
|
|
|
|
| 1 | 2 |
|
|
|
| 4 |
|
| 1 |
| 1 |
|
| 1 |
|
|
|
|
|
| 1 | 2 |
|
| 4 |
|
| 1 |
|
| 1 |
| 1 |
|
|
|
|
|
|
|
| 1 | 2 | 4 |
1 | 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 1 |
|
| 1 | 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
| 1 |
|
|
|
| 1 | 1 |
|
|
|
|
|
|
|
|
|
|
|
| 1 |
|
|
|
|
|
| 1 | 1 |
|
|
|
|
|
|
|
|
|
| 1 |
3. k-SAT归约成子集和
一般的k-SAT也可以归约到子集和，设子句数为m，变量数为n。那么设定目标值的高n位都是1，低m位都是k+1。
松弛变量的选择要依据能够产生1到k的最小非负整数集为准。例如k=6，那么松弛变量集应为｛1、2、3｝。此时目标值低m位应是7，那么子句选择值是1～6，总可以通过松弛变量选择使和值的对应位为7。
本文旨在解释k-SAT归约到子集和问题，故不谈证明。如若了解请看《算法导论》或其它相关书籍。
2015-12-17
https://blog.sciencenet.cn/blog-340399-943936.html
上一篇：多解的子句块关联段求解
下一篇：在中国科学原创被认可为什么这么难？
