文章目录

一、多项式时间规约 分析

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

一、多项式时间规约 分析

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

下图中 , 给定 输入 x \rm xx , 想要知道 x \rm xx 字符串 , 是否可以被 L \rm LL 语言对应的算法接受 ;

做一个规约 , 将上述问题 , 转化为 f ( x ) \rm f(x)f(x) 是否能被 L ′ \rm L'L

′

 语言对应的算法接受 ;

首先将 x \rm xx 字符串 , 输入到函数 f \rm ff 中计算 , 得到输出 f ( x ) \rm f(x)f(x) ,

然后将 f ( x ) \rm f(x)f(x) 输入到 L ′ \rm L'L

′

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

如果 L ′ \rm L'L

′

 接受 f ( x ) \rm f(x)f(x) , 那么就说 x \rm xx 是被 L \rm LL 所接受的 ;

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

NP 完全 定义 ★ :

如果 语言 B \rm BB 是 N P \rm NPNP 完全的 , 必须满足如下两个条件 :

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

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

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

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

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

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

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

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