博客

1.问题陈述：

3SAT问题：问题输入是一个子句集，每个子句都包含不超过3个文字。例如：

独立集：如果有一个顶点集合S，任意的两个顶点之间都没有边，则称为独立集。

2. 3SAT 到独立集的规约：

(1)  对于3SAT的每一个子句C=Z1+Z2+Z3 ，在图中构造三个点Z1,Z2,Z3 并且加入边{Z1,Z2|,{Z2,Z3}.{Z1,Z3}

(2我们将每一个子句，比如(x+y’+z)表示一个三角形，如图所示

那么对于独立集中只能从三个顶点中选择一个，再两条相反的符号间，存在一条额外的边，目标值g就是子句的数量，上例子的一个匹配图可以如图所示：

构造好这样的图后，我们想要给每个三角形赋值， 每条边是 冲突的，例如我们选择第一个三角形的y为真值后，与y相连的各个顶点将不能被选择。

加入了3m个点，3m+k条边所以是多项式的时间内完成的规约。