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

📅 آخر تحديث: ٢٧ يوليو ٢٠٢٦
✍️ نُشر في: ٢٧ يوليو ٢٠٢٦
📷 يحتوي على 26 صور
الموسوعة الحرة

في نظرية التعقيد الحسابي ، تُعدّ نظريات التسلسل الهرمي الزمني من أهمّ العبارات المتعلقة بالحساب المحدود زمنيًا على آلات تورينج . وبصورة مبسطة، تنصّ هذه النظريات على أنه إذا أُتيح لآلة تورينج وقتٌ أطول، فإنها تستطيع حلّ عددٍ أكبر من المسائل. على سبيل المثال، هناك مسائل يمكن حلّها في زمن n²، ولكن ليس في زمن n ، حيث n هو طول المدخلات.

تم إثبات نظرية التسلسل الزمني لآلات تورينغ الحتمية متعددة الأشرطة لأول مرة بواسطة ريتشارد إي. ستيرنز وجوريس هارتمانيس في عام 1965. [ 1 ] وقد تم تحسينها بعد عام عندما قام إف سي هيني وريتشارد إي. ستيرنز بتحسين كفاءة آلة تورينغ الشاملة . [ 2 ] ونتيجةً لهذه النظرية، لكل فئة تعقيد حتمية محدودة زمنيًا ، توجد فئة تعقيد محدودة زمنيًا أكبر منها تمامًا، وبالتالي فإن التسلسل الهرمي لفئات التعقيد المحدودة زمنيًا لا ينهار تمامًا. وبشكل أدق، تنص نظرية التسلسل الزمني لآلات تورينغ الحتمية على أنه بالنسبة لجميع الدوال f ( n ) القابلة للإنشاء زمنيًا ،دتيأنامهـ(o(و(ن)))⊊دتيأنامهـ(و(ن)سجل⁡و(ن))،{\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 ) تقاربياً.

وعلى وجه الخصوص، يُظهر هذا أندتيأنامهـ(نأ)⊊دتيأنامهـ(نب){\displaystyle {\mathsf {DTIME}}(n^{a})\subsetneq {\mathsf {DTIME}}(n^{b})}إذا وفقط إذاأ<ب{\displaystyle a<b}لذلك لدينا تسلسل هرمي زمني لا نهائي.

أُثبتت نظرية التسلسل الزمني لآلات تورينغ غير الحتمية لأول مرة على يد ستيفن كوك عام 1972. [ 3 ] ثم جرى تحسينها إلى شكلها الحالي عبر برهان معقد من قِبل جويل سيفراس ومايكل فيشر وألبرت ماير عام 1978. [ 4 ] وأخيرًا، في عام 1983، حقق ستانيسلاف زاك النتيجة نفسها بالبرهان البسيط الذي يُدرَّس اليوم. [ 5 ] تنص نظرية التسلسل الزمني لآلات تورينغ غير الحتمية على أنه إذا كانت g ( n ) دالة قابلة للإنشاء زمنيًا، و f ( n +1) = o ( g ( n ))، فإن شمالتيأنامهـ(و(ن))⊊شمالتيأنامهـ(ز(ن)).{\displaystyle {\mathsf {NTIME}}(f(n))\subsetneq {\mathsf {NTIME}}(g(n)).}

النظريات المماثلة للفضاء هي نظريات التسلسل الهرمي للفضاء . ولا توجد نظرية مماثلة معروفة لفئات التعقيد الاحتمالي المحدود زمنيًا، إلا إذا كانت الفئة تحتوي أيضًا على نصيحة واحدة . [ 6 ]

خلفية

تستخدم كلتا النظريتين مفهوم الدالة القابلة للإنشاء في الزمن . دالةو:شمال→شمال{\displaystyle f:\mathbb {N} \rightarrow \mathbb {N} }تكون قابلة للإنشاء في الزمن إذا وُجدت آلة تورينغ حتمية بحيث يكون لكلن∈شمال{\displaystyle n\in \mathbb {N} }إذا تم تشغيل الآلة بإدخال n من الواحدات، فسوف تتوقف بعد f ( n ) خطوة بالضبط. جميع كثيرات الحدود ذات المعاملات الصحيحة غير السالبة قابلة للإنشاء في زمن محدد، وكذلك الدوال الأسية مثل 2^ n .

نظرة عامة على البرهان

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

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

إفادة

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

دتيأنامهـ(o(و(ن)))⊊دتيأنامهـ(و(ن)سجل⁡و(ن)).{\displaystyle {\mathsf {DTIME}}(o(f(n)))\subsetneq {\mathsf {DTIME}}\left(f(n)\log f(n)\right).} وبعبارة أخرى، إذاو،ز{\displaystyle f,g}يمكن بناؤها زمنيًا، وو(ن)ln⁡و(ن)=o(ز(ن)){\displaystyle f(n)\ln f(n)=o(g(n))}، ثم

دتيأنامهـ(و(ن))⊊دتيأنامهـ(ز(ن)){\displaystyle {\mathsf {DTIME}}(f(n))\subsetneq {\mathsf {DTIME}}(g(n))}

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

مثال.دتيأنامهـ(ن)⊊دتيأنامهـ(ن(ln⁡ن)2){\displaystyle {\mathsf {DTIME}}(n)\subsetneq {\mathsf {DTIME}}(n(\ln n)^{2})}.

دليل

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

ولإثبات ذلك، نقوم أولاً بتعريف لغة ترميز الآلات ومدخلاتها التي تتسبب في توقفها في غضون f (| x |) خطوة: حو={([م]،x) | م يقبل x في و(|x|) خطوات}.{\displaystyle H_{f}=\left\{([M],x)\ |\ M\ {\text{يقبل}}\ x\ {\text{في}}\ f(|x|)\ {\text{خطوات}}\right\}.}

لاحظ هنا أن هذا فئة زمنية. إنها مجموعة أزواج الآلات والمدخلات لتلك الآلات ( 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 ) في زمن t).يا(تي(ن)⋅|م|){\displaystyle O(T(n)\cdot |M|)}على جهاز متعدد الأشرطة، حيث | M | هو طول ترميز M )، لدينا ما يلي: حو∈تيأنامهـ(و(م)3).{\displaystyle H_{f}\in {\mathsf {TIME}}\left(f(m)^{3}\right).}

وستُظهر بقية الأدلة ذلك حو∉تيأنامهـ(و(⌊م2⌋)){\displaystyle H_{f}\notin {\mathsf {TIME}}\left(f\left(\left\lfloor {\frac {m}{2}}\right\rfloor \right)\right)}

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

إذا كانت H f ضمن فئة التعقيد الزمني هذه، فإنه يوجد جهاز K ، عند إعطائه وصفًا للجهاز [ M ] ومدخلًا x ، يقرر ما إذا كانت المجموعة ([ M ]، x ) تنتمي إلى H f خلال تيأنامهـ(و(⌊م2⌋)).{\displaystyle {\mathsf {TIME}}\left(f\left(\left\lfloor {\frac {m}{2}}\right\rfloor \right)\right).}

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

إذا كان n هو طول المدخل إلى N ، فإن m (طول المدخل إلى K ) يساوي ضعف n مضافًا إليه رمز فاصل، أي m = 2n + 1. وبالتالي، يكون زمن تشغيل N هوتيأنامهـ(و(⌊م2⌋))=تيأنامهـ(و(⌊2ن+12⌋))=تيأنامهـ(و(ن)).{\displaystyle {\mathsf {TIME}}\left(f\left(\left\lfloor {\frac {m}{2}}\right\rfloor \right)\right)={\mathsf {TIME}}\left(f\left(\left\lfloor {\frac {2n+1}{2}}\right\rfloor \right)\right)={\mathsf {TIME}}\left(f(n)\right).}

الآن إذا أدخلنا [ 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 غير موجودة، وبالتالي حو∉تيأنامهـ(و(⌊م2⌋)).{\displaystyle H_{f}\notin {\mathsf {TIME}}\left(f\left(\left\lfloor {\frac {m}{2}}\right\rfloor \right)\right).}

امتداد

ربما أدرك القارئ أن البرهان يعطي نتيجة أضعف لأننا اخترنا محاكاة بسيطة لآلة تورينج، والتي نعرف عنها أن حو∈تيأنامهـ(و(م)3).{\displaystyle H_{f}\in {\mathsf {TIME}}(f(m)^{3}).}

من المعروف [ 7 ] أن هناك محاكاة أكثر كفاءة تثبت أن حو∈تيأنامهـ(و(م)سجل⁡و(م)).{\displaystyle H_{f}\in {\mathsf {TIME}}(f(m)\log f(m)).}

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

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

عواقب

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

على سبيل المثال،P⊊هـXPتيأنامهـ{\displaystyle {\mathsf {P}}\subsetneq {\mathsf {EXPTIME}}}منذP⊆دتيأنامهـ(2ن)⊊دتيأنامهـ(22ن)⊆هـXPتيأنامهـ{\displaystyle {\mathsf {P}}\subseteq {\mathsf {DTIME}}(2^{n})\subsetneq {\mathsf {DTIME}}(2^{2n})\subseteq {\mathsf {EXPTIME}}}. بالفعل،دتيأنامهـ(2ن)⊆دتيأنامهـ(o(22ن2ن))⊊دتيأنامهـ(22ن){\displaystyle {\mathsf {DTIME}}\left(2^{n}\right)\subseteq {\mathsf {DTIME}}\left(o\left({\frac {2^{2n}}{2n}}\right)\right)\subsetneq {\mathsf {DTIME}}(2^{2n})}من نظرية التسلسل الهرمي الزمني.

تضمن النظرية أيضًا وجود مسائل في P تتطلب أسسًا كبيرة جدًا لحلها؛ بمعنى آخر، لا يمكن اختزال P إلى DTIME ( nk ) لأي قيمة ثابتة لـ k . على سبيل المثال، توجد مسائل قابلة للحل في زمن n = 5000 ولكن ليس في زمن n = 4999. هذه إحدى الحجج ضد فرضية كوبام ، التي تنص على أن P فئة عملية من الخوارزميات. إذا حدث مثل هذا الاختزال، فيمكننا استنتاج أن P ≠ PSPACE ، نظرًا لأن من المعروف أن DTIME ( f ( n )) محتواة تمامًا في DSPACE ( f ( n )).

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

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

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

بالنسبة لهذه النماذج، تأخذ النظرية الشكل التالي:

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

وبالتالي، فإن زيادة عامل ثابت في الحد الزمني تسمح بحل المزيد من المسائل، على عكس الوضع بالنسبة لآلات تورينج (انظر نظرية التسريع الخطي ). علاوة على ذلك، أثبت بن عمرام [ 10 ] أنه في النماذج المذكورة أعلاه، بالنسبة لدالة f ذات معدل نمو متعدد الحدود (ولكنه أكبر من الخطي)، فإنه ينطبق على جميعε>0{\displaystyle \varepsilon >0}توجد مشكلة قرار لا يمكن حلها في أسوأ حالة زمنية حتمية f ( n )، ولكن يمكن حلها في أسوأ حالة زمنية(1+ε)و(ن){\displaystyle (1+\varepsilon )f(n)}.

انظر أيضاً

مراجع

  1. ↑ هارتمانيس، ج .؛ ستيرنز، ر. إي. (1 مايو 1965). "حول التعقيد الحسابي للخوارزميات" . معاملات الجمعية الرياضية الأمريكية . 117. الجمعية الرياضية الأمريكية: 285-306 . doi : 10.2307/1994208 . ISSN 0002-9947 . JSTOR 1994208. MR 0170805 .   
  2. ↑ هيني، إف سي؛ ستيرنز، آر إي (أكتوبر 1966). "محاكاة آلات تورينغ متعددة الأشرطة باستخدام شريطين" . مجلة ACM . 13 (4). نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM: 533-546 . doi : 10.1145/321356.321362 . ISSN 0004-5411 . S2CID 2347143 .  
  3. ↑ كوك، ستيفن أ. (1972). "تسلسل هرمي لتعقيد الوقت غير الحتمي". وقائع الندوة السنوية الرابعة لجمعية آلات الحوسبة حول نظرية الحوسبة . STOC '72. دنفر، كولورادو، الولايات المتحدة: جمعية آلات الحوسبة. الصفحات 187-192 . doi : 10.1145/800152.804913 . 
  4. ↑ سيفراس، جويل آي؛ فيشر، مايكل جيه ؛ ماير، ألبرت آر (يناير 1978). "فصل فئات التعقيد الزمني غير الحتمي" . مجلة ACM . 25 (1). نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM: 146-167 . doi : 10.1145/322047.322061 . ISSN 0004-5411 . S2CID 13561149 .  
  5. ^ شاك ، ستانيسلاف (أكتوبر 1983). "التسلسل الهرمي لآلة تورينج" . علوم الكمبيوتر النظرية . 26 (3). إلسفير ساينس بي في: 327–333 . دوى : 10.1016/0304-3975(83)90015-4 .
  6. ↑ فورتناو، ل.؛ سانثانام، ر. (2004). "نظريات التسلسل الهرمي للوقت متعدد الحدود الاحتمالي". الندوة السنوية الخامسة والأربعون لمعهد مهندسي الكهرباء والإلكترونيات حول أسس علوم الحاسوب . ص 316. doi : 10.1109/FOCS.2004.33 . ISBN  0-7695-2228-9. S2CID 5555450 . 
  7. ↑ سيبسر، مايكل (27 يونيو 2012). مقدمة في نظرية الحوسبة ( الطبعة الثالثة). سينجايج ليرنينج. ISBN  978-1-133-18779-0.
  8. ↑ سودبورو، إيفان هـ.؛ زالسبيرغ، أ. (1976). "حول عائلات اللغات المُعرَّفة بواسطة آلات الوصول العشوائي المحدودة زمنيًا". مجلة SIAM للحوسبة . 5 (2): 217-230 . doi : 10.1137/0205018 .
  9. ↑ جونز، نيل د. (1993). "عوامل الزمن الثابتة مهمة ". وقائع الندوة السنوية الخامسة والعشرين لجمعية آلات الحوسبة حول نظرية الحوسبة - STOC '93 . الصفحات 602-611 . doi : 10.1145/167088.167244 . ISBN  0-89791-591-7. S2CID 7527905 . 
  10. ↑ بن عمرام، أمير م. (2003). "تسلسلات زمنية أكثر إحكامًا ذات عامل ثابت". رسائل معالجة المعلومات . 87 (1): 39-44 . doi : 10.1016/S0020-0190(03)00253-9 .

للمزيد من القراءة