题目
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完全性。对于任意一个3SAT实例，如果其中某个子句中包含了同一个文字多次，那么可以缩减为一次；如果同时包含了某个变量的肯定及否定，那么可以将这个变量去掉。然后，再在每个子句中可以添加一些哑变量(即没用的辅助变量)，就可以将每个子句所包含的文字数目扩充到四个。至此，即已将该3SAT实例转化成了一个 EXACT 4SAT问题。
