这是简介的测试! 这是简介的测试! 这是简介的测试! 这是简介的测试!
3-3SAT问题NP-Complete性质的证明
3-3SAT问题
首先来说明一下这个记号,第一个$3$表示每个变量最多出现在$3$个子句中, 特别的,认为$\overline{x}$与$x$是一个变量,第二个$3$表示每个子句中最多出现3个变量。注意这里是最多,即有可能出现2个变量,或者一个变量。
值得讨论的事,如果每个子句中都确定性地存在3个变量,这个问题将脱离$NP-Complete$类,变成一个$P$问题.
从3SAT问题归约至3-3SAT问题
首先我们知道,要想实现这个归约,要解决的关键在于如何缩减一个变量的出现次数。
显然我们可以通过添加新的析取子句来达到这个目的。
可以通过真值表直接构造
a | b | a *b |
---|---|---|
1 | 1 | 1 |
0 | 0 | 1 |
1 | 0 | 0 |
0 | 1 | 0 |
以上就是要构造的子句
可以直接来化简一下
$$(a\bigcap b) \bigcup (\overline{a}\bigcap \overline{b})$$
化简得到
$$(b\bigcup \overline{a})\bigcap (a \bigcup \overline{b})$$
发现可以直接拆成两项
$$(b \bigcup \overline{a})\quad (a \bigcup \overline{b})$$
构造这两项的意义便是,如果存在这两个等式,那么a,b的值一定是相等的。
于是考虑在3SAT问题中出现的一系列出现$x$的表达式
一定可以通过这种方式将$x$拆成不同的变量,使得满足或不满足,可以发现一共只需要$n^2$级的代价。
证完了~