3 SAT归约到独立集问题

3-SAT归约到独立集问题 【3-SAT ≤p\leq_p≤p​ 独立集】 要证明3-SAT问题可以归约到独立集,就需要证明,有一个关于独立集的黑盒子,通过解3-SAT实例,能够解3-SAT问题。 图4为从3-SAT到独立集归约的一个实例。 图4 从3-SAT到独立集的归约 对于一个子句来说,只要有一项的值为真,则整个子句的值为真。 则,根据子句可以这样构造图:对于每一个子句,创建三个点,将三个点连接成三角形(如上图)。若存在两个子句中有x1x_1x1​和x ̅1\overline x_1x1​,则在这两个节点之间添加一条边(称为冲突变,即这两边不能同时被选到)。 则,存在一个真值赋值,当且仅