【计算理论】计算复杂性 ( 证明团问题是 NP 完全问题 )
文章目录
- 一、团问题是 NP 完全问题 证明思路
- 二、证明团问题是 NP 完全问题
一、团问题是 NP 完全问题 证明思路
证明一个命题是 NP\rm NPNP 完全问题 :
① 证明是 NP\rm NPNP 问题 : 首先证明该问题是 NP\rm NPNP 问题 ;
② 证明是最难的 NP\rm NPNP 问题 : 然后证明所有的 NP\rm NPNP 问题 , 可以在多项式时间内规约到 该命题中 ; 也可以使用一个已经证明的 NP\rm NPNP 完全问题 , 在多项式时间内规约到 需要被证明的命题 ;
证明 团问题 是 NP\rm NPNP 完全的 , 从已知的 NP\rm NPNP 完全问题出发 , 已知的 NP\rm NPNP 完全问题就是 3-SAT 问题 ,
如果 3-SAT 问题是 NP\rm NPNP 完全的话 ,
只要证明 3-SAT 问题 可以在 多项式时间内规约 到 团问题 中 , 3-SAT ≤\leq≤ 团问题 ,
就可以证明 团问题 是 NP\rm NPNP 完全问题 ;
将 3-SAT 问题 可以在 多项式时间内规约 到 团问题 中 ,
给定一个 3-SAT 问题 的 布尔逻辑公式 ,
ϕ=(x1∨x1∨x2)∧(x1‾∨x2‾∨x2‾)∧(x1‾∨x2∨x2)\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 )ϕ=(x1∨x1∨x2)∧(x1∨x2∨x2)∧(x1∨x2∨x2)
构造一个 无向图 ,
使得 布尔逻辑公式 是可满足的 , 当且仅当 , 无向图中有一个 k\rm kk 团 ;
k\rm kk 团就是无向图中 k\rm kk 个节点子集 , 每两个节点之间都有边相连 ;
证明过程 : 从 给定的 3-SAT 布尔逻辑公式 ϕ=(x1∨x1∨x2)∧(x1‾∨x2‾∨x2‾)∧(x1‾∨x2∨x2)\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 )ϕ=(x1∨x1∨x2)∧(x1∨x2∨x2)∧(x1∨x2∨x2) 中 , 构造出一个无向图 出来 , 使得该无向图可以满足 " 布尔逻辑公式 是可满足的 , 当且仅当 , 无向图中有一个 k\rm kk 团 "
二、证明团问题是 NP 完全问题
参考上篇博客 【计算理论】计算复杂性 ( 3-SAT 是 NP 完全问题 | 团问题是 NP 完全问题 | 团问题是 NP 完全问题证明思路 ) 三、团问题是 NP 完全问题 证明思路
从 给定的 3-SAT 布尔逻辑公式 ϕ=(x1∨x1∨x2)∧(x1‾∨x2‾∨x2‾)∧(x1‾∨x2∨x2)\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 )ϕ=(x1∨x1∨x2)∧(x1∨x2∨x2)∧(x1∨x2∨x2) 中 , 构造出一个无向图 出来 , 使得该无向图可以满足 " 布尔逻辑公式 是可满足的 , 当且仅当 , 无向图中有一个 k\rm kk 团 "
构造点集三元组 : 给定 3-SAT 合取范式 , 布尔逻辑公式中 , 每个子项都有一个三元组 ,
上图中的 无向图 左侧的 点集三元组 对应 布尔逻辑公式 合取范式 中的 (x1∨x1∨x2)\rm ( x_1 \lor x_1 \lor x_2 )(x1∨x1∨x2) 子项 ,
上图中的 无向图 顶部的 点集三元组 对应 布尔逻辑公式 合取范式 中的 (x1‾∨x2‾∨x2‾)\rm ( \overline{x_1} \lor \overline{x_2} \lor \overline{x_2} )(x1∨x2∨x2) 子项 ,
上图中的 无向图 右侧的 点集三元组 对应 布尔逻辑公式 合取范式 中的 (x1‾∨x2∨x2)\rm ( \overline{x_1} \lor x_2 \lor x_2 )(x1∨x2∨x2) 子项 ,
构造无向边 : 对于布尔逻辑公式 , 3-SAT 公式 ,
ϕ=(x1∨x1∨x2)∧(x1‾∨x2‾∨x2‾)∧(x1‾∨x2∨x2)\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 )ϕ=(x1∨x1∨x2)∧(x1∨x2∨x2)∧(x1∨x2∨x2)
如果要取值为真 , 需要每个子项取值都为真 ,
如果每个子项为真 , 每个子项都是析取式 , 只要保证每个子项中至少有一个为真即可 ,
在每个子项中取一个 词 为真的值 , 词的取值互相之间不发生矛盾 , 不能出现有一个词 是另外一个词的否定 , 词就是 原子命题变元 或其否定 ;
x1\rm x_1x1 与 x1‾\rm \overline{x_1}x1 互为否定 , 这两个节点之间不能有边相连 ,
x2\rm x_2x2 与 x2‾\rm \overline{x_2}x2 互为否定 , 这两个节点之间不能有边相连 ,
无向边构造原则 : 不同的 333 组点集之间 , 如果不是互为否定的 , 就连接一条边 , 本组之间没有边 ;
下图是构造好的无向图 :
证明 布尔逻辑公式 ϕ=(x1∨x1∨x2)∧(x1‾∨x2‾∨x2‾)∧(x1‾∨x2∨x2)\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 )ϕ=(x1∨x1∨x2)∧(x1∨x2∨x2)∧(x1∨x2∨x2) 是可满足的 , 当且仅当 , 无向图中有一个 3\rm 33 团 ;
取值 :
x1=false,x1‾=true\rm x_1 = false , \ \overline{x_1} = truex1=false, x1=true
x2=true,x2‾=false\rm x_2 = true, \ \overline{x_2} = falsex2=true, x2=false
x1∨x1∨x2=false∨false∨true=true\rm x_1 \lor x_1 \lor x_2 = false \lor false \lor true= truex1∨x1∨x2=false∨false∨true=true
x1‾∨x2‾∨x2‾=true∨true∨false=true\rm \overline{x_1} \lor \overline{x_2} \lor \overline{x_2} = true \lor true \lor false = truex1∨x2∨x2=true∨true∨false=true
x1‾∨x2∨x2=true∨true∨true=true\rm \overline{x_1} \lor x_2 \lor x_2 = true \lor true \lor true= truex1∨x2∨x2=true∨true∨true=true
上述取值时 , 合取范式中每个子项都为真 , 布尔逻辑公式取值为真 ;
找 333 团 : 在无向图中 , 找到一个 333 团 , 下图中红色的点组成的集合就是一个 333 团 , 可以发现取值为真的点都可以组成一个 333 团 ;
上图中 333 团 的规律就是找到 333 个取值为真的赋值 , 就可以自动找到一个 333 团 ;
总结
以上是生活随笔为你收集整理的【计算理论】计算复杂性 ( 证明团问题是 NP 完全问题 )的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： 【计算理论】计算复杂性 ( 3-SAT
- 下一篇： 【计算理论】计算复杂性 ( 无向图独立集