Deterministic time hierarchy
For time-constructible f,g≥n with f(n)log f(n)=o(g(n)), DTIME(f(n)) is a proper subset of DTIME(g(n)).
Key knowledge
For time-constructible f,g≥n with f(n)log f(n)=o(g(n)), DTIME(f(n)) is a proper subset of DTIME(g(n)). Diagonal simulation with padding gives a language requiring more than the smaller time bound. In particular DTIME(n²)⊊DTIME(n³).
Conditions and scope
- Use conventional deterministic multitape Turing machines; DTIME(t) means a worst-case O(t(n)) bound.
- Constructibility and the logarithmic simulation gap are part of this theorem. This separation within deterministic time does not resolve P versus NP.
Sources · 2
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Evidence and review
Theorem 3.4 and padded diagonalization proof, printed page 3; corroborating MIT Lecture 21 slides 10–11 separate o(t/log t) from O(t).
2026-10-10 · Independent AI editorial review: All241 compact claims, hypotheses, displayed equations/conventions and all596 origin semantic links read; entire241-entry author exact-source inspection matrix and declared limitations reviewed. Prior105 actual inherited Mathematics/Information records read for whole-inventory breadth. Targeted independent primary sections are listed below; this does NOT claim every cited source body or every proof was independently re-read. This is AI reference-content review, not human disciplinary certification, exhaustive textbook reproduction or experimental replication. Receipt: mathematics-information-independent-content-review.1.
Entry details
Permanent link to this entry ↗- Record identity
- info-deterministic-time-hierarchy
- Revision
- university-core.1
- Structured reference record
- University core expansion