你好赵伟

这个屌丝很懒，什么也没留下！

热门标签

【计算理论】计算理论总结 ( P 、NP 、NPC 总结 ) ★★

作者：你好赵伟 | 2024-03-09 13:18:50

踩

计算理论

文章目录

一、P 类
二、NP 类
三、NPC 类 ( NP 完全 )
四、P 、NP 、NPC 三者关系

一、P 类

$\rm P$ 类 : ★

所有能够被确定性单个带子图灵机 , 在多项式时间内 , 能够被判定的计算问题 ( 语言类 ) ,

将这些问题放在一起 ( 广义并集 $\bigcup$ ) , 组成一个整体 , 就称为 $\rm P$

符号化表示 : $\rm P = \bigcup_k TIME( n^k )$

$\rm P$ 类 , 就是定义有效算法所组成的类 ,

有效算法 , 就是在多项式时间内 , 可以执行完毕 , 得到一个确定的结果的算法 ;

确定的结果就是接受状态 , 或拒绝状态 ;

$\rm P$ 类有效算法示例 : ★

① PATH

② 贪心算法

③ 动态规划算法

④ REGULAR

⑤ CFL

参考博客 : 【计算理论】计算复杂性 ( P 类 | 有效算法函数 | NP 直觉 | NP 简介 | NP 类严格数学定义 )

二、NP 类

验证机 : $\rm A$ 语言 ( 计算问题 ) 的验证机 $\rm V$ ; ★

$\rm <w,c>$ 含义 : 给定一个输入 $\rm w$ , $\rm w$ 是输入字符串 , $\rm c$ 是输入 $\rm w$ 被接受的情况下的输入 , 即正确的输入 ;

$\rm A$ 语言 ( 计算问题 ) 的验证机 $\rm V$ 条件 : 给定了正确的输入 $\rm c$ , 让验证机 $\rm V$ 进行一步步验证 , 如果验证机 $\rm V$ 接受了输入的字符串 $\rm c$ , 称验证机 $\rm V$ 就是计算问题 $\rm A$ 的验证机 ;

符号化表示 : $\rm A = \{ w : 验证机 V 接受 <w,c> 中正确的输入 c \}$

验证操作 : 已经有了正确答案 $\rm c$ , 有一个有限的规则 , 将正确答案 $\rm c$ 每一步 , 代入有限规则中进行验证是否正确 ;

验证时间 : 已经有了正确答案 $\rm c$ , 有一个有限的规则 , 将正确答案 $\rm c$ 每一步 , 代入有限规则中进行验证是否正确 , 最后记录整个验证过程所花费的时间 ; 即学习的过程 ;

$\rm NP$ 计算问题要求 : 如果花费的时间在多项式时间之内 , 就称该问题是 $\rm NP$ 对应的计算问题 ;

多项式时间验证机 : $\rm A$ 语言如果可以在多项式时间内可以验证的话 , 就称该语言有一个多项式时间验证机 ; ★

$\rm NP$ 类就是有多项式时间验证机的语言类 ( 计算问题集合 ) ; ★

1 . $\rm NP$ 类算法举例 : ★

① 蛮力穷举算法 ;

2 . $\rm NP$ 类包含 $\rm NPC$ 类 ( $\rm NP$ 完全 ) , $\rm NPC$ 算法举例 : ★

① 布尔可满足性问题 SAT

② 3-SAT

③ 团问题 : 无向图中是否包含 $\rm k$ 团 , $\rm k$ 个节点两两之间有边相连 ;

④ 独立集问题

⑤ 顶点覆盖问题

⑥ 哈密顿路径问题

⑦ 旅行商问题

⑧ 子集和问题

3 . $\rm NP$ 类中 , 既不属于 $\rm P$ , 又不属于 $\rm NPC$ 的问题也是存在的 , 如 : ★

① 图同构问题

参考博客 :

三、NPC 类 ( NP 完全 )

NPC 是 NP-Completeness ( NP 完全 ) 的简称 ;

NP 完全定义 ★ :

如果语言 $\rm B$ 是 $\rm NP$ 完全的 , 必须满足如下两个条件 :

① 是 $\rm NP$ 问题 : 语言 $\rm B$ 对应的计算问题必须在 $\rm NP$ 中 , 换句话说就是可以找到一个多项式算法 , 可以验证该计算问题 ;

② 是 $\rm NP$ 最难问题 : 在 $\rm NP$ 中的任何计算问题 $\rm A$ , 都可以在多项式时间规约到 $\rm B$ , 也就是说在 $\rm NP$ 中的任何计算问题 , 其难易程度都不会超过 $\rm B$ , $\rm B$ 是 $\rm NP$ 中最难的问题 ;

$\rm NP$ 中其它所有的计算问题的难以长度都不会超过 $\rm B$ , $\rm B$ 问题是 $\rm NP$ 中最难的问题 ;

NP 完全命题 ★ : 如果 $\rm B$ 问题是 $\rm NP$ 完全的 , 并且 $\rm B$ 能在多项式时间规约到 $\rm C$ , 记作 $\rm B \leq C$ , 则 $\rm C$ 也是 $\rm NP$ 完全的 ;

该命题是很重要的命题 , 验证一个命题是 $\rm NP$ 完全的 , 需要满足上面的两个条件 , ① 是 $\rm NP$ 问题 , ② 是 $\rm NP$ 最难问题 ;

将计算问题与 $\rm NP$ 中最难问题 $\rm B$ 进行比较 , 是很难的 , 如果已经知道某个计算问题是 $\rm NP$ 完全的 , 就不需要与 $\rm NP$ 中所有问题进行比较 , 只与当前已知的 $\rm NP$ 完全问题比较即可 ;

将已知的 $\rm NP$ 完全的计算问题 $\rm B$ , 与要验证的 $\rm C$ 问题 , 进行规约 , 就知道 $\rm C$ 问题是否是 $\rm NP$ 完全的 ;

历史已经找到了一个 $\rm NP$ 完全问题 : 布尔可满足性问题 ( Boolean Satisfiability Problem；SAT ) ;

$\rm NP$ 类包含 $\rm NPC$ 类 ( $\rm NP$ 完全 ) , $\rm NPC$ 算法举例 : ★

① 布尔可满足性问题 SAT

② 3-SAT

③ 团问题 : 无向图中是否包含 $\rm k$ 团 , $\rm k$ 个节点两两之间有边相连 ;

④ 独立集问题

⑤ 顶点覆盖问题

⑥ 哈密顿路径问题

⑦ 旅行商问题

⑧ 子集和问题

参考博客 :

四、P 、NP 、NPC 三者关系

该观点目前认为是正确的 , 同样也没有严格的证明 ;

$\rm P \not= NP$ 情况分析 : 如果 $\rm P \not= NP$ , 则有

$\rm P < NP$ , ★

$\rm NP$ 完全 $\rm <NP$ ★

$\rm NP$ 问题中包含了三种计算问题 : ★

① $\rm P$ 问题

② $\rm NP$ 完全问题

③ 其它问题 , 既不属于 $\rm P$ 问题 , 又不属于 $\rm NP$ 完全问题 ;

图同构问题 , 就属于其它问题 , 既不属于 $\rm P$ 问题 , 又不属于 $\rm NP$ 完全问题 ;

$\rm NP$ 难问题 , 包含了 $\rm NP$ 完全问题 , 不包含 $\rm P$ 问题和 $\rm NP$ 中的其它问题 ;

在这里插入图片描述

参考博客 : 【计算理论】计算复杂性 ( NP 完全问题 | NP 难问题 P = NP 的情况 | NP 难问题 P ≠ NP 的情况 )

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/215162