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

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

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

$𝖣𝖳𝖨𝖬𝖤\left(o(f(n))\right)⊊𝖣𝖳𝖨𝖬𝖤(f(n)\log f(n))$ ,

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

وعلى وجه الخصوص، هذا يُظهر أن $𝖣𝖳𝖨𝖬𝖤(n^a)⊊𝖣𝖳𝖨𝖬𝖤(n^b)$ إذا وفقط إذا كان $a<b$، لذلك لدينا تسلسل هرمي زمني لانهائي.

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

$𝖭𝖳𝖨𝖬𝖤(f(n))⊊𝖭𝖳𝖨𝖬𝖤(g(n))$.

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

تمهيد

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

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

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

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

إفادة

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

$𝖣𝖳𝖨𝖬𝖤(o(f(n)))⊊𝖣𝖳𝖨𝖬𝖤(f(n)\log f(n)).$

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

مثال. هناك مشاكل يمكن حلها في زمن (n log² n) ولكن ليس في زمن n. يتبع ذلك تحديد $f(n)=n\log n$، حيث أن n في

$o(n\log n).$

البرهان

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

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

$H_f=\{([M],x)|M\text{accepts}x\text{in}f(|x|)\text{steps}\}.$

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

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

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

$H_f\in 𝖳𝖨𝖬𝖤(f(m{)}^3).$

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

$H_f\notin 𝖳𝖨𝖬𝖤\left(f\left(\lfloor \frac{m}{2}\rfloor \right)\right)$

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

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

$𝖳𝖨𝖬𝖤\left(f\left(\lfloor \frac{m}{2}\rfloor \right)\right).$

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

$𝖳𝖨𝖬𝖤\left(f\left(\lfloor \frac{m}{2}\rfloor \right)\right)=𝖳𝖨𝖬𝖤\left(f\left(\lfloor \frac{2n+1}{2}\rfloor \right)\right)=𝖳𝖨𝖬𝖤(f(n)).$

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

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

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

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

$H_f\notin 𝖳𝖨𝖬𝖤\left(f\left(\lfloor \frac{m}{2}\rfloor \right)\right).$

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

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

$H_f\in 𝖳𝖨𝖬𝖤(f(m{)}^3).$

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

$H_f\in 𝖳𝖨𝖬𝖤(f(m)\log f(m))$.

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

إذا كانت 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 ⊊....

على سبيل المثال، $𝖯⊊𝖤𝖷𝖯𝖳𝖨𝖬𝖤$ حيث $𝖯\subseteq 𝖣𝖳𝖨𝖬𝖤(2^n)⊊𝖣𝖳𝖨𝖬𝖤(2^{2n})\subseteq 𝖤𝖷𝖯𝖳𝖨𝖬𝖤$. بالفعل، $𝖣𝖳𝖨𝖬𝖤\left(2^n\right)\subseteq 𝖣𝖳𝖨𝖬𝖤\left(o\left(\frac{2^{2n}}{2n}\right)\right)⊊𝖣𝖳𝖨𝖬𝖤(2^{2n})$ من نظرية التسلسل الهرمي للزمن.

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

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

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

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

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

بالنسبة لهذه النماذج، تكون النظرية على الشكل التالي:

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

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

$\epsilon >0$

، توجد مشكلة قرار لا يمكن حلها في أسوأ وقت حتمي f (n) ولكن يمكن حلها في أسوأ وقت حتمي

$(1+\epsilon )f(n)$

.

انظر أيضا

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

قراءة إضافية

• قالب:استشهاد بكتاب Pages 310–313 of section 9.1: Hierarchy theorems.
• قالب:استشهاد بكتاب Section 7.2: The Hierarchy Theorem, pp. 143–146.