文章目录
一、多项式等价引入
二、多项式时间规约
一、多项式等价引入
计算复杂度 : 比较两个计算问题的复杂程度 , 首先求计算问题 时间复杂度的数量级 , 比较两个数量级的大小 , 进而得出 哪个计算问题的算法是更快的 ;
多项式等价 : 两个计算问题 , 如果要对比出它们中哪个计算问题更复杂一些 , 就需要使用到 多项式等价 ;
计算复杂度 是针对同一个计算问题 , 不同的计算模型所花费的时间 ;
多项式等价 是针对两个不同的计算问题 , 对比二者计算复杂度的差异 ;
集合论中 , 对比两个集合的大小 , 如果两个集合中的元素都存在一一映射 , 就说明两个集合是相等的 ;
自然数集 与 偶数集 , 这两个集合每个元素之间都存在一一映射 , 这两个集合的大小是一样大的 ;
二、多项式时间规约
多项式时间规约 :
给定两个语言 , 分别是 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 是一个 图灵机 ;
