【计算理论】计算复杂性 ( 3-SAT 是 NP 完全问题 | 团问题是 NP 完全问题 | 团问题是 NP 完全问题证明思路 )

文章目录

• 一、3-SAT 是 NP 完全问题
• 二、团问题是 NP 完全问题
• 三、团问题是 NP 完全问题 证明思路

一、3-SAT 是 NP 完全问题

布尔可满足性问题 ( Boolean Satisfiability Problem , SAT ) , 是

完全的 ;

3-SAT 问题 也是

完全问题 ;

3-SAT 问题 的逻辑公式 , 是由一些合取范式 , 这些合取范式中 , 每个子项中 , 所包含的 原子逻辑命题 或其否定命题 的 个数一定为

;

合取范式概念参考 【数理逻辑】范式 ( 合取范式 | 析取范式 | 大项 | 小项 | 极大项 | 极小项 | 主合取范式 | 主析取范式 | 等值演算方法求主析/合取范式 | 真值表法求主析/合取范式 ) ;

如下逻辑公式就是 3-SAT 问题逻辑公式 : 举例说明 :

SAT 与 3-SAT 问题是相互等价的 , 如果一般的命题逻辑公式

是可以满足的 , 当且仅当

逻辑公式也是可以满足的 ;

二、团问题是 NP 完全问题

团问题是 NP 完全问题

团 是一个无向图 点集 的 子集 , 使得 该点集子集 中 任何两个节点之间都有边相连 ;

团问题 就是 判定无向图中 , 是否包含有

个节点的 团 ;

上述团问题 , 是

问题 ;

给定一个无向图 , 其中有一个

个节点组成的集合 , 验证该

集合是否是团 ;

验证的方法就是看这

元集中的节点之间两两之间是否有边相连即可 ;

验证所花的时间是多项式时间 , 该计算问题在

中 ;

三、团问题是 NP 完全问题 证明思路

证明一个命题是

完全问题 :

① 证明是

问题 : 首先证明该问题是

问题 ;

② 证明是最难的

问题 : 然后证明所有的

问题 , 可以在多项式时间内规约到 该命题中 ; 也可以使用一个已经证明的

完全问题 , 在多项式时间内规约到 需要被证明的命题 ;

证明 团问题 是

完全的 , 从已知的

完全问题出发 , 已知的

完全问题就是 3-SAT 问题 ,

如果 3-SAT 问题是

完全的话 ,

只要证明 3-SAT 问题 可以在 多项式时间内规约 到 团问题 中 , 3-SAT

团问题 ,

就可以证明 团问题 是

完全问题 ;

将 3-SAT 问题 可以在 多项式时间内规约 到 团问题 中 ,

给定一个 3-SAT 问题 的 布尔逻辑公式 ,

构造一个 无向图 ,

使得 布尔逻辑公式 是可满足的 , 当且仅当 , 无向图中有一个

团 ;

团就是无向图中

个节点子集 , 每两个节点之间都有边相连 ;

证明过程 : 从 给定的 3-SAT 布尔逻辑公式

中 , 构造出一个无向图 出来 , 使得该无向图可以满足 " 布尔逻辑公式 是可满足的 , 当且仅当 , 无向图中有一个

团 "