一、多项式等价引入

计算复杂度 : 比较两个计算问题的复杂程度 , 首先求计算问题 时间复杂度的数量级 , 比较两个数量级的大小 , 进而得出 哪个计算问题的算法是更快的 ;

多项式等价 : 两个计算问题 , 如果要对比出它们中哪个计算问题更复杂一些 , 就需要使用到 多项式等价 ;

计算复杂度 是针对同一个计算问题 , 不同的计算模型所花费的时间 ;

多项式等价 是针对两个不同的计算问题 , 对比二者计算复杂度的差异 ;

集合论中 , 对比两个集合的大小 , 如果两个集合中的元素都存在一一映射 , 就说明两个集合是相等的 ;

自然数集 与 偶数集 , 这两个集合每个元素之间都存在一一映射 , 这两个集合的大小是一样大的 ;

二、多项式时间规约

多项式时间规约 :

给定两个语言 , 分别是 $\mathrm{L}$ , 和 ${\mathrm{L}}^{\prime }$ , 比较这两个语言的难易程度 ;
( 语言相当于算法 )

引入一个概念 , 多项式时间规约 , 记做 $\mathrm{L}\le {\mathrm{L}}^{\prime }$ ,

上述写法的含义是 : $\mathrm{L}$ 语言的难易程度 , 不会超过 ${\mathrm{L}}^{\prime }$ 的难易程度 ,

存在一个 多项式时间可计算函数 $\mathrm{f}:{\sum }^{\ast }\to {\sum }^{\ast }$ , 使得 $\mathrm{w}$ 字符串如果属于 $\mathrm{L}$ 语言 , 当且仅当 $\mathrm{f}(\mathrm{w})$ 属于 ${\mathrm{L}}^{\prime }$ ,

记做 : $\mathrm{w}\in \mathrm{L}\iff \mathrm{f}(\mathrm{w})\in {\mathrm{L}}^{\prime }$

核心问题是 判定字符串 $\mathrm{w}$ 是否属于 $\mathrm{L}$ 语言 ,

可以将该问题 , 规约到 ${\mathrm{L}}^{\prime }$ 语言上 ,

将 $\mathrm{w}$ 字符串输入到 多项式时间可计算函数 $\mathrm{f}$ 中 , 判定其输出 $\mathrm{f}(\mathrm{w})$ 是否属于 ${\mathrm{L}}^{\prime }$ 语言 ,

可以 将 $\mathrm{L}$ 的接受问题 , 转化为 ${\mathrm{L}}^{\prime }$ 的接受问题 ,

其连接的桥梁是 多项式时间可计算函数 $\mathrm{f}$ ;

多项式时间可计算函数 $\mathrm{f}$ 是一个 图灵机 ;

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/111184296