مبرهنة التسلسل الهرمي الزمني

في نظرية التعقيد الحسابي، تعتبر نظريات التسلسل الهرمي الزمني   هي عبارات مهمة حول الحوسبة المحدودة بالوقت على آلات تورينج. وبصورة غير رسمية، فإن هذه النظريات تقول أنه إذا توفر المزيد من الوقت، يمكن لآلة تورينج حل المزيد من المشاكل. على سبيل المثال، هناك مشاكل يمكن حلها باستخدام n2 من الزمن ولكن ليس n من الزمن، حيث n هو طول المدخلات.

أمكن إثبات نظرية التسلسل الهرمي الزمني لآلات تورينج متعددة الأشرطة الحتمية لأول مرة بواسطة ريتشارد إي ستيرنز وجوريس هارتمانيس في عام 1965. وقد جري تحسين ذلك الإثبات بعد عام واحد عندما قام FC Hennie و Richard E. Stearns بتحسين كفاءة آلة تورينج العامة. وبناءً على النظرية، فإن لكل فئة تعقيد محدودة بالوقت حتمية، توجد فئة تعقيد محدودة بالوقت أكبر بشكل صارم، وبالتالي فإن التسلسل الهرمي المحدود بالوقت لفئات التعقيد لا ينهار تمامًا. وبتعبير أدق، تنص نظرية التسلسل الزمني للآلات تورينج الحتمية على أنه بالنسبة لجميع  f (n)،

  ,

حيث يشير DTIME ( f (n)) إلى فئة التعقيد لمشاكل القرار القابلة للحل في الوقت O ( f (n)). تتضمن الفئة اليسرى القليل من تدوين o، حيث تشير إلى مجموعة مشاكل القرار التي يمكن حلها في وقت أقل من f (n) تقريبًا.

وعلى وجه الخصوص، هذا يُظهر أن  إذا وفقط إذا كان ، لذلك لدينا تسلسل هرمي زمني لانهائي.

أمكن إثبات نظرية التسلسل الهرمي الزمني للآلات تورينج غير الحتمية لأول مرة بواسطة ستيفن كوك في عام 1972. ثم جرى تحسينه إلى شكله الحالي من خلال إثبات معقد بواسطة جويل سيفيراس، ومايكل فيشر، وألبرت ماير في عام 1978. وأخيرًا، في عام 1983، توصل ستانيسلاف زاك Stanislav Žák إلى نفس النتيجة باستخدام الإثبات البسيط الذي يجري تدريسه اليوم. تنص نظرية التسلسل الهرمي الزمني لآلات تورينج غير الحتمية على أنه إذا كانت g (n) دالة قابلة للبناء الزمني، و f (n +1) = o ( g (n))، فإن:

 .

النظريات المُناظرة للفضاء هي نظريات التسلسل الهرمي للفضاء space hierarchy theorems. لا توجد نظرية مماثلة معروفة لفئات التعقيد الاحتمالي المحدودة بالوقت، ما لم يكن للفئة أيضًا Advice واحد.

 تمهيد 
تستخدم كلتا النظريتين مفهوم الدالة القابلة للبناء في الزمن time-constructible function. حيث دالة  يمكن بناؤها زمنيًا إذا كانت هناك آلة تورينج حتمية بحيث يكون لكل  إذا جرى تشغيل الماكينة بإدخال n من الـ واحد، فسوف تتوقف بعد f (n) خطوة على وجه التحديد. جميع متعددات الحدود ذات المعاملات الصحيحة غير السالبة قابلة للبناء زمنيًا، كما هي الحال مع الدوال الأسية مثل 2n.

 نظرة عامة على الإثبات 
نحن بحاجة إلى إثبات أن بعض فئات الوقت TIME ( g (n)) أكبر تمامًا من بعض فئات الوقت TIME ( f (n)). ونقوم بذلك عن طريق بناء آلة لا يمكن أن تكون في الزمن TIME(f(n))، عن طريق عملية القطر diagonalization. ثم نُظهر أن الآلة موجودة في الزمن TIME(g(n))، وذلك باستخدام جهاز محاكاة.

 نظرية التسلسل الزمني الحتمي 

 إفادة 
نظرية التسلسل الزمني. إذا كانت f (n) دالة قابلة للإنشاء زمنيًا، فهناك مشكلة قرار لا يمكن حلها في أسوأ حالة زمنية حتمية o (f (n)) ولكن يمكن حلها في أسوأ حالة زمنية حتمية O (f (n)log f (n)). هكذا

 ملاحظة 1. f (n) هي على الأقل n، نظرًا لأن الدوال الأصغر لا يمكن إنشاؤها زمنيًا أبدًا.

مثال. هناك مشاكل يمكن حلها في زمن (n log2 n) ولكن ليس في زمن n. يتبع ذلك تحديد ، حيث أن n في



 البرهان 
لقد قمنا هنا بتضمين دليل على نتيجة أضعف، ألا وهي أن DTIME (f (n)) هي مجموعة فرعية صارمة من DTIME ( f (2n+1)3)، حيث أنها أبسط ولكنها توضح فكرة الإثبات. انظر أسفل هذا القسم للحصول على معلومات حول كيفية توسيع الدليل إلى f (n)log f (n).

ولإثبات ذلك، قمنا أولاً بتعريف لغة ترميزات الآلات ومدخلاتها التي تتسبب في توقفها خلال f



لاحظ هنا أن هذه هوي الفئة الزمنية. إنها مجموعة أزواج الآلات والمدخلات لتلك الآلات ( M، x ) بحيث تقبل الآلة M ضمن f (| x |) من الخطوات.

هنا، M هي آلة تورينج حتمية، و x هو مدخلها (المحتويات الأولية لشريطها). [ M ] يشير إلى إدخال يُشفِّر آلة تورينج M. نفرض أن m يكون حجم المجموعة ([ M ]، x ).

نحن نعلم أنه يمكننا تحديد عضوية Hf عن طريق آلة تورينج حتمية R، والتي تحاكي M لـ f (x) من الخطوات عن طريق حساب f (| x |) أولاً ثم كتابة صف من الأصفار بهذا الطول، ثم استخدام هذا الصف من الأصفار كـ "ساعة" أو "عداد" لمحاكاة M على الأكثر لهذا العدد من الخطوات. في كل خطوة، تحتاج آلة المحاكاة إلى النظر في تعريف M لتقرر ما سيكون الإجراء التالي. من الآمن أن نقول إن هذا يستغرق على الأكثر f (m)3 من العمليات (نظرًا لأنه من المعروف أنه يمكن تحقيق محاكاة لآلة ذات تعقيد زمني T (n) في الوقت  على جهاز متعدد الأشرطة، حيث | M | هو طول ترميز M )، لدينا ما يلي:



وسوف يُظهر باقي البرهان أن



لذلك إذا استبدلنا 2n + 1 بـ m، نحصل على النتيجة المطلوبة. لنفترض أن Hf تنتمي إلى فئة التعقيد الزمني هذه، وسوف نصل إلى تناقض.

إذا كان Hf ضمن فئة تعقيد الوقت هذه، فهناك آلة K، والتي، بناءً على وصف الآلة [ M ] والمُدخل x، تُقرر ما إذا كانت المجموعة ([ M ]، x ) ضمن Hf ضمن



نستخدم هذا الـ K لإنشاء آلة أخرى، N، والتي تأخذ وصف الآلة [ M ] وتشغل K على المجموعة ([ M ]، [ M ])، أي. يجري محاكاة M على الكود الخاص به بواسطة K، ثم يقبل N إذا رُفض K، ويرفض إذا قُبل K. إذا كان n هو طول المدخل إلى N، فإن m (طول المدخل إلى K ) يساوي ضعف n بالإضافة إلى رمز فاصل، لذا فإن m = 2 n + 1. ويكون وقت تشغيل N هو هكذا



الآن إذا قمنا بإدخال [ N ] كمدخل إلى N نفسها (وهو ما يجعل n طول [ N ]) وطرحنا السؤال عما إذا كان N يقبل وصفه الخاص كمُدخل، فسنحصل على:

 إذا كانت N تقبل [ N ] (ونحن نعلم أنها تفعل ذلك في عمليات f (n) على الأكثر حيث تتوقف K عند ([ N ]، [ N ]) في f (n)) من الخطوات، فهذا يعني أن K ترفض ([ N ]، [ N ])، وبالتالي فإن ([ N ]، [ N ]) ليست في Hf، وبالتالي وفقًا لتعريف Hf، فهذا يعني أن N لا تقبل [ N ] في f (n)من الخطوات. تناقض.

 إذا كانت N ترفض [ N ] (ونحن نعلم أنها كذلك في أكثر من عملية f (n))، فهذا يعني أن K يقبل ([ N ]، [ N ])، وبالتالي فإن ([ N ]، [ N ]) موجود في Hf، وبالتالي فإن N يقبل [ N ] في f (n) من الخطوات. تناقض.

نستنتج من ذلك أن الآلة K غير موجودة، وبالتالي



 امتداد للنظرية 
ربما أدرك القارئ أن الإثبات يعطي النتيجة الأضعف، لأننا اخترنا محاكاة آلة تورينج البسيطة التي نعلم أنها



ومن المعروف أن هناك محاكاة أكثر كفاءة تثبت أن:

 .

 نظرية التسلسل الهرمي للزمن غير الحتمي 
إذا كانت g (n) دالة قابلة للإنشاء زمنيًا، و f (n+1) = o ( g (n))، فهناك مشكلة قرار لا يمكن حلها في زمن غير حتمي f (n) ولكن يمكن حلها في زمن غير حتمي g (n). أو بعبارة أخرى، فئة التعقيد NTIME ( f (n)) هي مجموعة فرعية صارمة من NTIME ( g (n)).

 العواقب 
تضمن نظريات التسلسل الهرمي للوقت أن الإصدارات الحتمية وغير الحتمية للتسلسل الهرمي الأسي exponential hierarchy هي تسلسلات هرمية حقيقية: أو بعبارة أخرى P ⊊ EXPTIME ⊊ 2-EXP ⊊... و NP ⊊ NEXPTIME ⊊ 2-NEXP ⊊....

على سبيل المثال،  حيث . بالفعل،  من نظرية التسلسل الهرمي للزمن.

تؤكد النظرية أيضًا وجود مشكلات في P تتطلب أسسًا كبيرة بشكل اختياري لحلها؛ بعبارة أخرى، لا تنهار P إلى DTIME (nk) لأي k ثابت. على سبيل المثال، توجد مشكلات يمكن حلها في n5000 مرة ولكن ليس n4999 مرة. هذه إحدى الحجج ضد أطروحة كوبهام Cobham's thesis، وهي التي تنص على أن P هي فئة عملية من الخوارزميات. إذا حدث مثل هذا الانهيار، فيمكننا استنتاج أن P ≠ PSPACE، نظرًا لأنه من المعروف أن DTIME ( f (n)) محصور بشكل صارم في DSPACE ( f (n)).

ومع ذلك، فإن نظريات التسلسل الزمني لا تقدم أي وسيلة لربط التعقيد الحتمي وغير الحتمي، أو تعقيد الزمن والمكان، وبالتالي فإنها لا تلقي الضوء على الأسئلة العظيمة التي لم يجري حلها في نظرية التعقيد الحسابي وهي: ما إذا كان P و NP، أو NP و PSPACE، أو PSPACE و EXPTIME، أو EXPTIME و NEXPTIME متساويين أم لا.

 نظريات التسلسل الهرمي الأكثر حدة 
الفجوة بمقدار  بين الحد الزمني الأدنى والأعلى في نظرية التسلسل الهرمي يمكن إرجاعها إلى كفاءة الجهاز المستخدم في الإثبات، أي برنامج عالمي يحافظ على عدد الخطوات. ويمكن القيام بذلك بكفاءة أكبر على نماذج حسابية معينة. وقد جرى إثبات النتائج الأكثر وضوحًا، والتي يمكن تقديمها أدناه، في:

 آلة الوصول العشوائي random-access machine بتكلفة الوحدة
 نموذج لغة برمجة تعمل برامجه على شجرة ثنائية يجري الوصول إليها دائمًا عبر جذرها. هذا النموذج، الذي قدمه نيل د. جونز Neil D. Jones يُعد أقوى من آلة تورينج الحتمية ولكنه أضعف من آلة الوصول العشوائي.

بالنسبة لهذه النماذج، تكون النظرية على الشكل التالي:إذا كانت f (n) دالة قابلة للإنشاء زمنيًا، فهناك مشكلة قرار لا يمكن حلها في أسوأ حالة زمنية حتمية f (n) ولكن يمكن حلها في أسوأ حالة زمنية af (n) لبعض الثوابت a (تعتمد على f ).وبالتالي، فإن الزيادة في الحد الزمني بعامل ثابت تسمح بحل المزيد من المشاكل، على النقيض من الوضع بالنسبة لآلات تورينج (انظر نظرية التسريع الخطي Linear speedup theorem). علاوة على ذلك، أثبت بن عمرام Ben-Amram أنه في النماذج المذكورة أعلاه، بالنسبة لـ f من معدل النمو متعدد الحدود (ولكن أكثر من خطي)، فإن الحالة هي أنه بالنسبة لكل ، توجد مشكلة قرار لا يمكن حلها في أسوأ وقت حتمي f (n) ولكن يمكن حلها في أسوأ وقت حتمي .

 انظر أيضا 

 نظرية التسلسل الهرمي للفضاء Space hierarchy theorem

 المراجع 

 قراءة إضافية 

  Pages 310–313 of section 9.1: Hierarchy theorems.
  Section 7.2: The Hierarchy Theorem, pp. 143–146.

تصنيف:مقالات تحوي براهين
تصنيف:مبرهنات التعقيد الحسابي