在計算複雜度理論內，時間階層定理（Time hierarchy theorems）是一個有關圖靈機時間限制上面一系列重要的定理。用不大正式的說法解釋，這理論告訴我們圖靈機在給予更多時間之後，保證能解決更多的問題。
舉例：必然存在問題是圖靈機可以用n2的時間解決，但是不能用n的時間解決。
參考資料
- Pages 310–313 of section 9.1: Hierarchy theorems.
- Section 7.2: The Hierarchy Theorem, pp. 143–146.
在計算複雜度理論內，時間階層定理（Time hierarchy theorems）是一個有關圖靈機時間限制上面一系列重要的定理。用不大正式的說法解釋，這理論告訴我們圖靈機在給予更多時間之後，保證能解決更多的問題。
舉例：必然存在問題是圖靈機可以用n2的時間解決，但是不能用n的時間解決。
參考資料
评论 (0)