時間譜系理論

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP




在計算複雜度理論內,時間譜系理論(Time hierarchy theorems)是一個有關圖靈機時間限制上面一個重要的理論。用不大正式的說法解釋,這理論告訴我們圖靈機在給予更多時間之後,保證能解決更多的問題。


舉例:必然存在問題是圖靈機可以用n2的時間解決,但是不能用n的時間解決。



參考資料





  • Michael Sipser. Introduction to the Theory of Computation. PWS Publishing. 1997. ISBN 0-534-94728-X.  Pages 310–313 of section 9.1: Hierarchy theorems.


  • Christos Papadimitriou. Computational Complexity 1st. Addison Wesley. 1993. ISBN 0-201-53082-1.  Section 7.2: The Hierarchy Theorem, pp. 143–146.

Popular posts from this blog

倭马亚王朝

Gabbro

托萊多 (西班牙)