8.8
In the EXACT 4SAT problem, the input is a set of clauses, each of which is a disjunction of exactly four literals, and such that each variable occurs at most once in each clause. The goal is to find a satisfying assignment, if one exists. Prove that EXACT 4SAT is NP-complete.
证明
首先很显然，EXACT 4SAT属于NP。现在通过将3SAT归约到EXACT 4SAT来证明后者的NP完全性。
1. 对于任意一个3SAT实例，如果其中某个子句中包含了同一个文字多次，那么可以缩减为一次。
如：(x∨y∨y∨y)可以变为(x∨y)
2. 如果同时包含了某个变量的肯定及否定，那么可以将这个变量去掉。
如：(x∨y∨~y)可以变为(x)
3. 然后，可以再在每个子句中可以添加一些无关变量，这样就可以将每个子句所包含的文字数目扩充到四个。
如：(x∨y∨z)可以变为(x∨y∨z∨a)(x∨y∨z∨~a)
下面证明这种转换是等价的：
① 若(x∨y∨z)为真，无论a是否为真，(x∨y∨z∨a)和(x∨y∨z∨~a)都为真，即(x∨y∨z∨a)(x∨y∨z∨~a)为真。
② 若(x∨y∨z∨a)(x∨y∨z∨~a)为真，即(x∨y∨z∨a)和(x∨y∨z∨~a)都为真。
1) 若a为真，那么~a为假，则(x∨y∨z)必须为真，否则(x∨y∨z∨~a)为假。
2) 若a为假，则(x∨y∨z)必须为真，否则(x∨y∨z∨a)为假。
因此这种转换是等价的。
至此，即已将3SAT问题归约到了EXACT 4SAT问题。由于3SAT为NP完全问题，所以4SAT也是NP完全问题。
