時間譜系理論

维基百科,自由的百科全书
跳转至: 导航搜索

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

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

參考資料[编辑]