【计算理论】计算复杂性 ( 多项式时间规约 | NP 完全 ★ | 布尔可满足性问题 ) ★

文章目录

• 一、多项式时间规约 分析
• 二、NP 完全 ★ ( 计算理论最重要的概念 )

一、多项式时间规约 分析

多项式时间规约概念 : 【计算理论】计算复杂性 ( 多项式等价引入 | 多项式时间规约 )

下图中 , 给定 输入

, 想要知道

字符串 , 是否可以被

语言对应的算法接受 ;

做一个规约 , 将上述问题 , 转化为

是否能被

语言对应的算法接受 ;

首先将

字符串 , 输入到函数

中计算 , 得到输出

,

然后将

输入到

算法中 , 查看该输入是否能被接受 ,

如果

接受

, 那么就说

是被

所接受的 ;

二、NP 完全 ★ ( 计算理论最重要的概念 )

NP 完全 定义 ★ :

如果 语言

是

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

① 是

问题 : 语言

对应的计算问题必须在

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

② 是

最难问题 : 在

中的任何计算问题

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

, 也就是说在

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

,

是

中最难的问题 ;

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

,

问题是

中最难的问题 ;

NP 完全命题 ★ : 如果

问题是

完全的 , 并且

能在 多项式时间规约 到

, 记作

, 则

也是

完全的 ;

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

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

问题 , ② 是

最难问题 ;

将计算问题与

中最难问题

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

完全的 , 就不需要与

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

完全问题比较即可 ;

将 已知的

完全的 计算问题

, 与 要验证的

问题 , 进行规约 , 就知道

问题是否是

完全的 ;

历史已经找到了一个

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