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

文章目录

一、多项式等价引入

二、多项式时间规约





一、多项式等价引入


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


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



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


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



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


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






二、多项式时间规约


多项式时间规约 :


给定两个语言 , 分别是 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 是一个 图灵机 ;


上一篇:java异常集锦(一)


下一篇:趋势科技PC-cillin2015,你来公測我发奖!