في نظرية التعقيد الحسابي، تعتبر نظريات التسلسل الهرمي الزمني (بالإنجليزية: time hierarchy theorems) هي عبارات مهمة حول الحوسبة المحدودة بالوقت على آلات تورينج. وبصورة غير رسمية، فإن هذه النظريات تقول أنه إذا توفر المزيد من الوقت، يمكن لآلة تورينج حل المزيد من المشاكل. على سبيل المثال، هناك مشاكل يمكن حلها باستخدام n2 من الزمن ولكن ليس n من الزمن، حيث n هو طول المدخلات.
أمكن إثبات نظرية التسلسل الهرمي الزمني لآلات تورينج متعددة الأشرطة الحتمية لأول مرة بواسطة ريتشارد إي ستيرنز وجوريس هارتمانيس في عام 1965. وقد جري تحسين ذلك الإثبات بعد عام واحد عندما قام FC Hennie و Richard E. Stearns بتحسين كفاءة آلة تورينج العامة. وبناءً على النظرية، فإن لكل فئة تعقيد محدودة بالوقت حتمية، توجد فئة تعقيد محدودة بالوقت أكبر بشكل صارم، وبالتالي فإن التسلسل الهرمي المحدود بالوقت لفئات التعقيد لا ينهار تمامًا. وبتعبير أدق، تنص نظرية التسلسل الزمني للآلات تورينج الحتمية على أنه بالنسبة لجميع الدوال القابلة للبناء زمنيًا f (n)،
D
T
I
M
E
(
o
(
f
(
n
)
)
)
⊊
D
T
I
M
E
(
f
(
n
)
log
f
(
n
)
)
{\displaystyle {\mathsf {DTIME}}\left(o\left(f(n)\right)\right)\subsetneq {\mathsf {DTIME}}(f(n){\log f(n)})}
,
حيث يشير DTIME ( f (n)) إلى فئة التعقيد لمشاكل القرار القابلة للحل في الوقت O ( f (n)). تتضمن الفئة اليسرى القليل من تدوين o، حيث تشير إلى مجموعة مشاكل القرار التي يمكن حلها في وقت أقل من f (n) تقريبًا.
وعلى وجه الخصوص، هذا يُظهر أن
D
T
I
M
E
(
n
a
)
⊊
D
T
I
M
E
(
n
b
)
{\displaystyle {\mathsf {DTIME}}(n^{a})\subsetneq {\mathsf {DTIME}}(n^{b})}
إذا وفقط إذا كان
a
<
b
{\displaystyle a
، لذلك لدينا تسلسل هرمي زمني لانهائي.
أمكن إثبات نظرية التسلسل الهرمي الزمني للآلات تورينج غير الحتمية لأول مرة بواسطة ستيفن كوك في عام 1972. ثم جرى تحسينه إلى شكله الحالي من خلال إثبات معقد بواسطة جويل سيفيراس، ومايكل فيشر، وألبرت ماير في عام 1978. وأخيرًا، في عام 1983، توصل ستانيسلاف زاك Stanislav Žák إلى نفس النتيجة باستخدام الإثبات البسيط الذي يجري تدريسه اليوم. تنص نظرية التسلسل الهرمي الزمني لآلات تورينج غير الحتمية على أنه إذا كانت g (n) دالة قابلة للبناء الزمني، و f (n +1) = o ( g (n))، فإن:
N
T
I
M
E
(
f
(
n
)
)
⊊
N
T
I
M
E
(
g
(
n
)
)
{\displaystyle {\mathsf {NTIME}}(f(n))\subsetneq {\mathsf {NTIME}}(g(n))}
.
النظريات المُناظرة للفضاء هي نظريات التسلسل الهرمي للفضاء space hierarchy theorems. لا توجد نظرية مماثلة معروفة لفئات التعقيد الاحتمالي المحدودة بالوقت، ما لم يكن للفئة أيضًا Advice واحد.