文章目录

一、团问题是 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 团 ;