课程期末作业：《算法概论》课后8.16题的证明

题目：

证明：考虑怎么把一个3SAT实例转化成一个EXPERIMENTAL CUISINE问题:对于任意 一个 3SAT 问题，若其某一子句c为(U ∨V ∨W)，我们可以相应地建立 7 种
ingredients，分别为{UVWc ,UVWc ,UVWc ,UVWc ,UVWc ,UVWc ,UVWc}。这 7 种 ingredients 代表了使得子句 c 成立的七种不同情况，比如UWVc 代表U 和W 同时为
真，且V 为假。它们之间当然是完全不兼容的，因此将其中两两之间的 discord 值设 为 1。现在再考虑子句与子句之间的情况，对于任意两子句 i 和 j ，将这两个子句中
相矛盾的成分之间的 discord 值设为 1，比如UABi 与UCDj 等。设子句总数为n， 再令 p = 0 ，若此时能选择的成份数为 n ，那么即说明此 3SAT 能满足。另外，判断
一个3SAT是否能满足与找出这个3SAT的解实际上是等价的(可以参考Ex.8.2)， 因此若 EXPERIMENTAL CUISINE 在多项式时间内可解的话，3SAT 亦然。