0%

3-3SAT问题NP完全性证明

这是简介的测试! 这是简介的测试! 这是简介的测试! 这是简介的测试!

这是简介的测试!

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$级的代价。

证完了~

abab