三元可满足性问题是NPC问题

三元可满足性问题是NPC问题
定理7.如果 Y 是一个 NP 完全问题, X 属于 NP ,且 Y \leq_p X,则 XNP 完全的。
之前已经证明3-SAT是一个NP问题,可以通过证明电路可满足性 \leq_P 3-SAT,来证明它是NP完全的。
【电路可满足性 \leq_P 3-SAT】
对于一个电路K,对于电路的每一个结点v,关联一个变量x_v , x_v表示在该结点的真值。电路K的门计算有3种:与、或、非。
如果某个结点v是非门,则它的唯一进入边来自于结点u,那么必须要有x_v= \overline x_u,可以通过添加两个子句(x_v \vee x_u)或(\overline x_v \vee \overline x_u)来保证这一点。
如果某个结点v是或门,则它的2个边分别来自于结点u和w,那么必须要有x_v= x_u \vee x_w,可以通过添加三个子句(x_v \vee \overline x_u)、(x_v \vee \overline x_w)或(\overline x_v \vee x_u \vee x_w)来保证这一点。
如果某个结点v是与门,则它的2个边分别来自于结点u和w,那么必须要有x_v= x_u \wedge x_w,可以通过添加三个子句(\overline x_v \vee x_u)、(\overline x_v \vee x_w)或(x_v \vee \overline x_u \vee \overline x_w)来保证这一点。
对于源结点,保证其等于规定的值,可以对每个源结点v添加一个只含有一个项x_v\overline x_v的子句,强迫其取规定的值。对于输出结点,添加一个单变量子句,让其取1。于是完成了构造。
可以证明构造的SAT实例是等价于与给定的电路可满足性实例的。
由于我们要证明电路可满足性 \leq_P 3-SAT,因此还需要将子句转换为恰好有3个变量的实例。
对于只有一个项t的子句,可以将子句替换成(t \vee z_1 \vee z_2);
对于有2个项的子句(t \vee t’),可以替换成(t \vee t’ \vee z_1)。
显然,为了保证新构造的子句等价于原来的子句,需要保证z_1=z_2=0
为了保证z_1=z_2=0,对于i=1和2,可以添加子句(\overline z_i \vee z_3 \vee z_4),(\overline z_i \vee \overline z_3 \vee z_4),(\overline z_i \vee z_3 \vee \overline z_4),(\overline z_i \vee \overline z_3 \vee \overline z_4),保证z_1=z_2=0
从而完成了电路K到3-SAT的构造。因此电路可满足性 \leq_P 3-SAT。证毕。
因此,根据3-SAT \leq_p 独立集 \leq_p 顶点覆盖 \leq_p 集合覆盖,可以得到独立集、顶点覆盖、集合包装、集合覆盖问题都是NPC问题。

0

Leave a Reply

Your email address will not be published.