文章目錄

• 證明 非確定性圖靈機(jī) 與 確定性圖靈機(jī) 的時(shí)間復(fù)雜度 之間的指數(shù)關(guān)系

證明 非確定性圖靈機(jī) 與 確定性圖靈機(jī) 的時(shí)間復(fù)雜度 之間的指數(shù)關(guān)系

---

在上一篇博客 【計(jì)算理論】計(jì)算復(fù)雜性 ( 非確定性圖靈機(jī)的時(shí)間復(fù)雜度 | 非確定性圖靈機(jī) 與 確定性圖靈機(jī) 的時(shí)間復(fù)雜度 之間的關(guān)系 ) 中 , 提出如下命題 :

使用 確定性圖靈機(jī) , 模仿 非確定性圖靈機(jī) , 在 計(jì)算效率方面要付出一定的代價(jià) , 計(jì)算復(fù)雜度會(huì) 指數(shù)級(jí)增加 ;

如果 非確定性 單個(gè)帶子 圖靈機(jī) , 時(shí)間復(fù)雜度是 $\mathrm{O}(\mathrm{t}(\mathrm{n}))$ ,

找到一個(gè) 等價(jià)的 確定性 單個(gè)帶子 圖靈機(jī) , 其時(shí)間復(fù)雜度是 $2^{\mathrm{O}(\mathrm{t}(\mathrm{n}))}$ ;

證明上述命題 :

給定 非確定性圖靈機(jī) , 找到一個(gè)確定性圖靈機(jī) , 模仿該 非確定圖靈機(jī) , 實(shí)際上是沿著 非確定性圖靈機(jī) 計(jì)算樹(shù) 最長(zhǎng)的分支 , 進(jìn)行模仿 ;

如何找到 計(jì)算樹(shù) 的最長(zhǎng)分支呢 , 即 沿著 計(jì)算樹(shù) 進(jìn)行 寬度優(yōu)先搜索 :

假設(shè)計(jì)算樹(shù)的高度是 $\mathrm{f}(\mathrm{n})$ , 該計(jì)算樹(shù)在最壞的情況下 , 要走的步數(shù) , 主要決定于 樹(shù)的節(jié)點(diǎn)個(gè)數(shù) ,

如果 計(jì)算樹(shù) 的高度是 $\mathrm{f}(\mathrm{n})$ , 計(jì)算樹(shù)的節(jié)點(diǎn)個(gè)數(shù)的數(shù)量級(jí)是 $2^{\mathrm{f}(\mathrm{n})}$ 數(shù)量級(jí) ; ( 計(jì)算二叉樹(shù)的節(jié)點(diǎn) , 最壞的情況下就是滿(mǎn)二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù) )

確定性圖靈機(jī) 與 非確定性圖靈機(jī) 計(jì)算相同的問(wèn)題 , 計(jì)算的時(shí)間 滿(mǎn)足如下關(guān)系 :

如果 非確定性圖靈機(jī) 所花費(fèi)的時(shí)間是 $\mathrm{t}(\mathrm{n})$ ,

則 確定性圖靈機(jī) 所花費(fèi)的時(shí)間是 $2^{\mathrm{t}(\mathrm{n})}$ ;

總結(jié)

以上是生活随笔為你收集整理的【计算理论】计算复杂性 ( 证明 非确定性图灵机 与 确定性图灵机 的时间复杂度 之间的指数关系 )的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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