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

文章目录

一、多项式等价引入

二、多项式时间规约

一、多项式等价引入

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

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

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

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

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

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

二、多项式时间规约

多项式时间规约 :

给定两个语言 , 分别是 L \rm LL , 和 L ′ \rm L'L

′

 , 比较这两个语言的难易程度 ;

( 语言相当于算法 )

引入一个概念 , 多项式时间规约 , 记做 L ≤ L ′ \rm L \leq L'L≤L

′

 ,

上述写法的含义是 : L \rm LL 语言的难易程度 , 不会超过 L ′ \rm L'L

′

 的难易程度 ,

存在一个 多项式时间可计算函数 f : ∑ ∗ → ∑ ∗ \rm f : \sum^* \to \sum^*f:∑

∗

→∑

∗

 , 使得 w \rm ww 字符串如果属于 L \rm LL 语言 , 当且仅当 f ( w ) \rm f(w)f(w) 属于 L ′ \rm L'L

′

 ,

记做 : w ∈ L ⇔ f ( w ) ∈ L ′ \rm w \in L \Leftrightarrow f(w) \in L'w∈L⇔f(w)∈L

′

核心问题是 判定字符串 w \rm ww 是否属于 L \rm LL 语言 ,

可以将该问题 , 规约到 L ′ \rm L'L

′

 语言上 ,

将 w \rm ww 字符串输入到 多项式时间可计算函数 f \rm ff 中 , 判定其输出 f ( w ) \rm f(w)f(w) 是否属于 L ′ \rm L'L

′

 语言 ,

可以 将 L \rm LL 的接受问题 , 转化为 L ′ \rm L'L

′

 的接受问题 ,

其连接的桥梁是 多项式时间可计算函数 f \rm ff ;

多项式时间可计算函数 f \rm ff 是一个 图灵机 ;