文章目录
一、3-SAT 是 NP 完全问题
二、团问题是 NP 完全问题
三、团问题是 NP 完全问题 证明思路
一、3-SAT 是 NP 完全问题
布尔可满足性问题 ( Boolean Satisfiability Problem , SAT ) , 是 N P \rm NPNP 完全的 ;
3-SAT 问题 也是 N P \rm NPNP 完全问题 ;
3-SAT 问题 的逻辑公式 , 是由一些合取范式 , 这些合取范式中 , 每个子项中 , 所包含的 原子逻辑命题 或其否定命题 的 个数一定为 3 \rm 33 ;
合取范式概念参考 【数理逻辑】范式 ( 合取范式 | 析取范式 | 大项 | 小项 | 极大项 | 极小项 | 主合取范式 | 主析取范式 | 等值演算方法求主析/合取范式 | 真值表法求主析/合取范式 ) ;
如下逻辑公式就是 3-SAT 问题逻辑公式 : 举例说明 :
( a 1 ∨ a 2 ∨ z 1 ) ∧ ( z 1 ‾ ∨ a 3 ∨ z 2 ) ∧ ( z 2 ‾ ∨ a 4 ∨ z 3 ) ∧ ⋯ ∧ ( z l − 3 ‾ ∨ a l − 1 ∨ a l ) \rm ( a_1 \lor a_2 \lor z_1 ) \land ( \overline{z_1} \lor a_3 \lor z_2 ) \land ( \overline{z_2} \lor a_4 \lor z_3 ) \land \cdots \land ( \overline{z_{l-3}} \lor a_{l-1} \lor a_l )(a
1
∨a
2
∨z
1
)∧(
z
1
∨a
3
∨z
2
)∧(
z
2
∨a
4
∨z
3
)∧⋯∧(
z
l−3
∨a
l−1
∨a
l
)
SAT 与 3-SAT 问题是相互等价的 , 如果一般的命题逻辑公式 ( a 1 ∨ a 2 ∨ ⋯ ∨ a l ) \rm ( a_1 \lor a_2 \lor \cdots \lor a_l )(a
1
∨a
2
∨⋯∨a
l
) 是可以满足的 , 当且仅当 ( a 1 ∨ a 2 ∨ z 1 ) ∧ ( z 1 ‾ ∨ a 3 ∨ z 2 ) ∧ ( z 2 ‾ ∨ a 4 ∨ z 3 ) ∧ ⋯ ∧ ( z l − 3 ‾ ∨ a l − 1 ∨ a l ) \rm ( a_1 \lor a_2 \lor z_1 ) \land ( \overline{z_1} \lor a_3 \lor z_2 ) \land ( \overline{z_2} \lor a_4 \lor z_3 ) \land \cdots \land ( \overline{z_{l-3}} \lor a_{l-1} \lor a_l )(a
1
∨a
2
∨z
1
)∧(
z
1
∨a
3
∨z
2
)∧(
z
2
∨a
4
∨z
3
)∧⋯∧(
z
l−3
∨a
l−1
∨a
l
) 逻辑公式也是可以满足的 ;
二、团问题是 NP 完全问题
团问题是 NP 完全问题
团 是一个无向图 点集 的 子集 , 使得 该点集子集 中 任何两个节点之间都有边相连 ;
团问题 就是 判定无向图中 , 是否包含有 k \rm kk 个节点的 团 ;
上述团问题 , 是 N P \rm NPNP 问题 ;
给定一个无向图 , 其中有一个 n \rm nn 个节点组成的集合 , 验证该 n \rm nn 集合是否是团 ;
验证的方法就是看这 n \rm nn 元集中的节点之间两两之间是否有边相连即可 ;
验证所花的时间是多项式时间 , 该计算问题在 N P \rm NPNP 中 ;
三、团问题是 NP 完全问题 证明思路
证明一个命题是 N P \rm NPNP 完全问题 :
① 证明是 N P \rm NPNP 问题 : 首先证明该问题是 N P \rm NPNP 问题 ;
② 证明是最难的 N P \rm NPNP 问题 : 然后证明所有的 N P \rm NPNP 问题 , 可以在多项式时间内规约到 该命题中 ; 也可以使用一个已经证明的 N P \rm NPNP 完全问题 , 在多项式时间内规约到 需要被证明的命题 ;
证明 团问题 是 N P \rm NPNP 完全的 , 从已知的 N P \rm NPNP 完全问题出发 , 已知的 N P \rm NPNP 完全问题就是 3-SAT 问题 ,
如果 3-SAT 问题是 N P \rm NPNP 完全的话 ,
只要证明 3-SAT 问题 可以在 多项式时间内规约 到 团问题 中 , 3-SAT ≤ \leq≤ 团问题 ,
就可以证明 团问题 是 N P \rm NPNP 完全问题 ;
将 3-SAT 问题 可以在 多项式时间内规约 到 团问题 中 ,
给定一个 3-SAT 问题 的 布尔逻辑公式 ,
ϕ = ( x 1 ∨ x 1 ∨ x 2 ) ∧ ( x 1 ‾ ∨ x 2 ‾ ∨ x 2 ‾ ) ∧ ( x 1 ‾ ∨ x 2 ∨ x 2 ) \rm \phi = ( x_1 \lor x_1 \lor x_2 ) \land ( \overline{x_1} \lor \overline{x_2} \lor \overline{x_2} ) \land ( \overline{x_1} \lor x_2 \lor x_2 )ϕ=(x
1
∨x
1
∨x
2
)∧(
x
1
∨
x
2
∨
x
2
)∧(
x
1
∨x
2
∨x
2
)
构造一个 无向图 ,
使得 布尔逻辑公式 是可满足的 , 当且仅当 , 无向图中有一个 k \rm kk 团 ;
k \rm kk 团就是无向图中 k \rm kk 个节点子集 , 每两个节点之间都有边相连 ;
证明过程 : 从 给定的 3-SAT 布尔逻辑公式 ϕ = ( x 1 ∨ x 1 ∨ x 2 ) ∧ ( x 1 ‾ ∨ x 2 ‾ ∨ x 2 ‾ ) ∧ ( x 1 ‾ ∨ x 2 ∨ x 2 ) \rm \phi = ( x_1 \lor x_1 \lor x_2 ) \land ( \overline{x_1} \lor \overline{x_2} \lor \overline{x_2} ) \land ( \overline{x_1} \lor x_2 \lor x_2 )ϕ=(x
1
∨x
1
∨x
2
)∧(
x
1
∨
x
2
∨
x
2
)∧(
x
1
∨x
2
∨x
2
) 中 , 构造出一个无向图 出来 , 使得该无向图可以满足 " 布尔逻辑公式 是可满足的 , 当且仅当 , 无向图中有一个 k \rm kk 团 "
