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

这是简介的测试!

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

证完了~