在计算复杂度理论内，时间阶层定理（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.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
