2 可满足性问题

2.1 SAT和3-SAT

【SAT问题】
将布尔可满足性问题(Boolean satisfiability problem)叫做SAT:
给定变量集 X={{x_1,x_2,…,x_n}} 上的一组子句 C_1,C_2,…,C_n ,问存在满足的真值赋值吗?
例如,设有3个子句:(x_1 \vee \overline {x_2} ),(\overline {x_1} \vee \overline {x_3} ),(x_2 \vee \overline {x_3} ),那么如果让所有的变量都为1,则不能够满足所有的子句,因为第二个子句的值为0。
【3-SAT问题】
3-SAT问题也叫作三元可满足性问题。因为每个子句恰好包含三个项。
3-SAT问题可以描述为:
给定变量集 X={{x_1,x_2,…,x_n}} 上的一组子句 C_1,C_2,…,C_n ,每一个子句的长度为3,问存在满足的真值赋值吗?

2.2 3-SAT归约到独立集问题

【3-SAT \leq_p 独立集】
要证明3-SAT问题可以归约到独立集,就需要证明,有一个关于独立集的黑盒子,通过解3-SAT实例,能够解3-SAT问题。
图4为从3-SAT到独立集归约的一个实例。
在这里插入图片描述
图4 从3-SAT到独立集的归约
对于一个子句来说,只要有一项的值为真,则整个子句的值为真。
则,根据子句可以这样构造图:==对于每一个子句,创建三个点,将三个点连接成三角形(如上图)。若存在两个子句中有x_1\overline x_1,,则在这两个节点之间添加一条边==(称为冲突变,即这两边不能同时被选到)。
则,存在一个真值赋值,当且仅当在每个子句中拿一个节点,且有一个大小为m(子句个数)的独立集。
例如,在图4中,有大小为3的独立集{x_1,x_3, x_4},,分别取这三个值为1,可以使得所有子句的真值都为1,即子句的合取为1,这组子句是可满足的。

2.3 归约的传递性

归约之间存在传递性。
定理4.如果 X \leq_p Y, Y \leq_p Z,,则 X \leq_p Z
通过上述归约,可以得到:
3-SAT \leq_p 独立集 \leq_p 顶点覆盖 \leq_p 集合覆盖

0
Posted in 算法设计与分析

Leave a Comment:

电子邮件地址不会被公开。