文章目录

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

一、P 类

类 : ★

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

将这些问题放在一起 ( 广义并集

) , 组成一个整体 , 就称为

符号化表示 :

类 , 就是定义 有效算法 所组成的类 ,

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

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

类有效算法示例 : ★

① PATH

② 贪心算法

③ 动态规划算法

④ REGULAR

⑤ CFL

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

二、NP 类

验证机 :

语言 ( 计算问题 ) 的 验证机

; ★

含义 : 给定一个 输入

,

是输入字符串 ,

是输入

被接受的情况下的输入 , 即正确的输入 ;

语言 ( 计算问题 ) 的 验证机

条件 : 给定了正确的输入

, 让验证机

进行一步步验证 , 如果 验证机

接受了输入的字符串

, 称 验证机

就是计算问题

的验证机 ;

符号化表示 :

验证操作 : 已经有了正确答案

, 有一个有限的规则 , 将正确答案

每一步 , 代入有限规则中进行验证是否正确 ;

验证时间 : 已经有了正确答案

, 有一个有限的规则 , 将正确答案

每一步 , 代入有限规则中进行验证是否正确 , 最后记录整个验证过程所花费的时间 ; 即 学习的过程 ;

计算问题要求 : 如果花费的时间 在 多项式时间 之内 , 就称 该问题是

对应的计算问题 ;

多项式时间验证机 :

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

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

1 .

类算法举例 : ★

① 蛮力穷举算法 ;

2 .

类包含

类 (

完全 ) ,

算法举例 : ★

① 布尔可满足性问题 SAT

② 3-SAT

③ 团问题 : 无向图中是否包含

团 ,

个节点两两之间有边相连 ;

④ 独立集问题

⑤ 顶点覆盖问题

⑥ 哈密顿路径问题

⑦ 旅行商问题

⑧ 子集和问题

3 .

类中 , 既不属于

, 又不属于

的问题也是存在的 , 如 : ★

① 图同构问题

参考博客 :

• 【计算理论】计算复杂性 ( P 类 | 有效算法函数 | NP 直觉 | NP 简介 | NP 类严格数学定义 )
• 【计算理论】计算复杂性 ( NP 完全问题 - 布尔可满足性问题 ★ | 布尔可满足性问题是 NP 完全问题证明思路 ) ★
• 【计算理论】计算复杂性 ( 3-SAT 是 NP 完全问题 | 团问题是 NP 完全问题 | 团问题是 NP 完全问题证明思路 )
• 【计算理论】计算复杂性 ( NP 完全问题 | 顶点覆盖问题 | 哈密顿路径问题 | 旅行商问题 | 子集和问题 )
• 【计算理论】计算复杂性 ( NP 完全问题 | NP 难 问题 P = NP 的情况 | NP 难 问题 P ≠ NP 的情况 )

三、NPC 类 ( NP 完全 )

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

NP 完全 定义 ★ :

如果 语言

是

完全的 , 必须满足如下两个条件 :

① 是

问题 : 语言

对应的计算问题必须在

中 , 换句话说就是可以找到一个多项式算法 , 可以验证该计算问题 ;

② 是

最难问题 : 在

中的任何计算问题

, 都可以在 多项式时间规约 到

, 也就是说在

中的任何计算问题 , 其难易程度都不会超过

,

是

中最难的问题 ;

中其它所有的计算问题的难以长度都不会超过

,

问题是

中最难的问题 ;

NP 完全命题 ★ : 如果

问题是

完全的 , 并且

能在 多项式时间规约 到

, 记作

, 则

也是

完全的 ;

该命题是很重要的命题 , 验证一个命题是

完全的 , 需要满足上面的两个条件 , ① 是

问题 , ② 是

最难问题 ;

将计算问题与

中最难问题

进行比较 , 是很难的 , 如果已经知道某个计算问题是

完全的 , 就不需要与

中所有问题进行比较 , 只与当前已知的

完全问题比较即可 ;

将 已知的

完全的 计算问题

, 与 要验证的

问题 , 进行规约 , 就知道

问题是否是

完全的 ;

历史已经找到了一个

完全问题 : 布尔可满足性问题 ( Boolean Satisfiability Problem；SAT ) ;

类包含

类 (

完全 ) ,

算法举例 : ★

① 布尔可满足性问题 SAT

② 3-SAT

③ 团问题 : 无向图中是否包含

团 ,

个节点两两之间有边相连 ;

④ 独立集问题

⑤ 顶点覆盖问题

⑥ 哈密顿路径问题

⑦ 旅行商问题

⑧ 子集和问题

参考博客 :

• 【计算理论】计算复杂性 ( P 类 | 有效算法函数 | NP 直觉 | NP 简介 | NP 类严格数学定义 )
• 【计算理论】计算复杂性 ( 多项式时间规约 | NP 完全 ★ | 布尔可满足性问题 ) ★
• 【计算理论】计算复杂性 ( NP 完全问题 - 布尔可满足性问题 ★ | 布尔可满足性问题是 NP 完全问题证明思路 ) ★
• 【计算理论】计算复杂性 ( 3-SAT 是 NP 完全问题 | 团问题是 NP 完全问题 | 团问题是 NP 完全问题证明思路 )
• 【计算理论】计算复杂性 ( NP 完全问题 | 顶点覆盖问题 | 哈密顿路径问题 | 旅行商问题 | 子集和问题 )
• 【计算理论】计算复杂性 ( NP 完全问题 | NP 难 问题 P = NP 的情况 | NP 难 问题 P ≠ NP 的情况 )

四、P 、NP 、NPC 三者关系

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

情况分析 : 如果

, 则有

, ★

完全

★

问题 中包含了三种计算问题 : ★

①

问题

②

完全问题

③ 其它问题 , 既不属于

问题 , 又不属于

完全问题 ;

图同构问题 , 就属于 其它问题 , 既不属于

问题 , 又不属于

完全问题 ;

难 问题 , 包含了

完全问题 , 不包含

问题 和

中的其它问题 ;

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