这是简介的测试! 这是简介的测试! 这是简介的测试! 这是简介的测试!
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$级的代价。
证完了~