文章目錄

• 一、多項(xiàng)式等價(jià)引入
• 二、多項(xiàng)式時(shí)間規(guī)約

一、多項(xiàng)式等價(jià)引入

---

計(jì)算復(fù)雜度 : 比較兩個(gè)計(jì)算問(wèn)題的復(fù)雜程度 , 首先求計(jì)算問(wèn)題 時(shí)間復(fù)雜度的數(shù)量級(jí) , 比較兩個(gè)數(shù)量級(jí)的大小 , 進(jìn)而得出 哪個(gè)計(jì)算問(wèn)題的算法是更快的 ;

多項(xiàng)式等價(jià) : 兩個(gè)計(jì)算問(wèn)題 , 如果要對(duì)比出它們中哪個(gè)計(jì)算問(wèn)題更復(fù)雜一些 , 就需要使用到 多項(xiàng)式等價(jià) ;

計(jì)算復(fù)雜度 是針對(duì)同一個(gè)計(jì)算問(wèn)題 , 不同的計(jì)算模型所花費(fèi)的時(shí)間 ;

多項(xiàng)式等價(jià) 是針對(duì)兩個(gè)不同的計(jì)算問(wèn)題 , 對(duì)比二者計(jì)算復(fù)雜度的差異 ;

集合論中 , 對(duì)比兩個(gè)集合的大小 , 如果兩個(gè)集合中的元素都存在一一映射 , 就說(shuō)明兩個(gè)集合是相等的 ;

自然數(shù)集 與 偶數(shù)集 , 這兩個(gè)集合每個(gè)元素之間都存在一一映射 , 這兩個(gè)集合的大小是一樣大的 ;

二、多項(xiàng)式時(shí)間規(guī)約

---

多項(xiàng)式時(shí)間規(guī)約 :

給定兩個(gè)語(yǔ)言 , 分別是 $\mathrm{L}$ , 和 ${\mathrm{L}}^{\prime }$ , 比較這兩個(gè)語(yǔ)言的難易程度 ;
( 語(yǔ)言相當(dāng)于算法 )

引入一個(gè)概念 , 多項(xiàng)式時(shí)間規(guī)約 , 記做 $\mathrm{L}\le {\mathrm{L}}^{\prime }$ ,

上述寫(xiě)法的含義是 : $\mathrm{L}$ 語(yǔ)言的難易程度 , 不會(huì)超過(guò) ${\mathrm{L}}^{\prime }$ 的難易程度 ,

存在一個(gè) 多項(xiàng)式時(shí)間可計(jì)算函數(shù) $\mathrm{f}:{\sum }^{?}\to {\sum }^{?}$ , 使得 $\mathrm{w}$ 字符串如果屬于 $\mathrm{L}$ 語(yǔ)言 , 當(dāng)且僅當(dāng) $\mathrm{f}(\mathrm{w})$ 屬于 ${\mathrm{L}}^{\prime }$ ,

記做 : $\mathrm{w}\in \mathrm{L}?\mathrm{f}(\mathrm{w})\in {\mathrm{L}}^{\prime }$

核心問(wèn)題是 判定字符串 $\mathrm{w}$ 是否屬于 $\mathrm{L}$ 語(yǔ)言 ,

可以將該問(wèn)題 , 規(guī)約到 ${\mathrm{L}}^{\prime }$ 語(yǔ)言上 ,

將 $\mathrm{w}$ 字符串輸入到 多項(xiàng)式時(shí)間可計(jì)算函數(shù) $\mathrm{f}$ 中 , 判定其輸出 $\mathrm{f}(\mathrm{w})$ 是否屬于 ${\mathrm{L}}^{\prime }$ 語(yǔ)言 ,

可以 將 $\mathrm{L}$ 的接受問(wèn)題 , 轉(zhuǎn)化為 ${\mathrm{L}}^{\prime }$ 的接受問(wèn)題 ,

其連接的橋梁是 多項(xiàng)式時(shí)間可計(jì)算函數(shù) $\mathrm{f}$ ;

多項(xiàng)式時(shí)間可計(jì)算函數(shù) $\mathrm{f}$ 是一個(gè) 圖靈機(jī) ;

總結(jié)

以上是生活随笔為你收集整理的【计算理论】计算复杂性 ( 多项式等价引入 | 多项式时间规约 )的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。