مرجع
آخر الزيارات

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

1٬595 كلمة•0 مشاهدة•🗒️ منذ 3 أيام
باختصار: في نظرية التعقيد الحسابي، تعتبر نظريات التسلسل الهرمي الزمني هي عبارات مهمة حول الحوسبة المحدودة بالوقت على آلات تورينج. تجد هنا «نظرية التسلسل الهرمي للزمن غير الحتمي»، «قراءة إضافية» و«العواقب» ضمن 12 قسماً.
المحتويات
  1. نظرية التسلسل الهرمي للزمن غير الحتمي
  2. قراءة إضافية
  3. العواقب
  4. امتداد للنظرية
  5. وسوف يُظهر باقي البرهان أن
  6. نظريات التسلسل الهرمي الأكثر حدة
  7. ,
  8. البرهان
  9. نظرة عامة على الإثبات
  10. تمهيد
  11. إفادة
  12. آلة الوصول العشوائي random-access machine بتكلفة الوحدة

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

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

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

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

قراءة إضافية

Pages 310–313 of section 9.1: Hierarchy theorems.

Section 7.2: The Hierarchy Theorem, pp. 143–146.

العواقب

ومن ناحية أخرى، تؤكد النظرية كذلك وجود مشكلات في 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 متساويين أم لا.

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

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

امتداد للنظرية

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

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

.

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

علاوةً على ذلك، إذا كان 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 ] (ونحن نعلم أنها كذلك في أكثر من عملية f (n))، فهذا يعني أن K يقبل ([ N ]، [ N ])، وبالتالي فإن ([ N ]، [ N ]) موجود في Hf، وبالتالي فإن N يقبل [ N ] في f (n) من الخطوات. تناقض.

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

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

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

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

نظريات التسلسل الهرمي الأكثر حدة

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

,

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

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

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

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

.

البرهان

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

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

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

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

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

نظرة عامة على الإثبات

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

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

تمهيد

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

إفادة

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

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

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

آلة الوصول العشوائي 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
  • المراجع

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.