وقت الخبرة

الموسوعة الحرة

في نظرية التعقيد الحسابي ، فإن فئة التعقيد EXPTIME (تسمى أحيانًا EXP أو DEXPTIME ) هي مجموعة جميع مشاكل القرار التي يمكن حلها بواسطة آلة تورينج حتمية في وقت أسي ، أي في وقت O (2 p ( n ) )، حيث p ( n ) هي دالة متعددة الحدود لـ n .

يُعدّ EXPTIME فئةً بديهيةً ضمن تسلسل هرمي أُسّي لفئات التعقيد، حيث تزداد تعقيدًا مع تزايد تعقيد مُعاملات التنبؤ أو مُبدّلات الكميات. على سبيل المثال، تُعرَّف الفئة 2-EXPTIME بشكلٍ مُشابهٍ لـ EXPTIME، ولكن بحدٍّ زمنيٍّ أُسّيٍّ مُضاعف . يُمكن تعميم هذا التعريف ليشمل حدودًا زمنيةً أعلى فأعلى.

يمكن أيضًا إعادة صياغة EXPTIME كفئة الفضاء APSPACE، وهي مجموعة جميع المشاكل التي يمكن حلها بواسطة آلة تورينج المتناوبة في الفضاء متعدد الحدود.

ترتبط فئة EXPTIME بفئات التعقيد الزمني والمكاني الأساسية الأخرى على النحو التالي: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE . علاوة على ذلك، وبحسب نظرية التسلسل الهرمي الزمني ونظرية التسلسل الهرمي المكاني ، يُعرف أن P ⊊ EXPTIME وNP ⊊ NEXPTIME وPSPACE ⊊ EXPSPACE.

التعريف الرسمي

فيما يتعلق بـ DTIME ،

هـXPتيأنامهـ=⋃ك∈شمالدتيأنامهـ(2نك).{\displaystyle {\mathsf {EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}\left(2^{n^{k}}\right).}

العلاقات مع الصفوف الأخرى

من المعروف أن

P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE

وأيضًا، وفقًا لنظرية التسلسل الهرمي الزمني ونظرية التسلسل الهرمي المكاني ، فإن

P ⊊ EXPTIME، NP ⊊ NEXPTIME و PSPACE ⊊ EXPSPACE

في التعبيرات أعلاه، يرمز الرمز ⊆ إلى "مجموعة جزئية من"، ويرمز الرمز ⊊ إلى "مجموعة جزئية صارمة من".

لذا، يجب أن يكون واحد على الأقل من أول ثلاثة تضمينات، وواحد على الأقل من آخر ثلاثة تضمينات، صحيحًا، ولكن لا يُعرف أيها صحيح. ومن المعروف أيضًا أنه إذا كانت P = NP ، فإن EXPTIME = NEXPTIME ، وهي فئة المسائل التي يمكن حلها في وقت أسي بواسطة آلة تورينج غير حتمية . [ 1 ] بتعبير أدق، E ≠ NE إذا وفقط إذا وُجدت لغات متفرقة في NP غير موجودة في P. [ 2 ]

يمكن إعادة صياغة EXPTIME كفئة الفضاء APSPACE، وهي مجموعة جميع المسائل التي يمكن حلها بواسطة آلة تورينغ متناوبة في فضاء متعدد الحدود. هذه إحدى طرق إثبات أن PSPACE ⊆ EXPTIME، لأن آلة تورينغ المتناوبة لا تقل قوة عن آلة تورينغ الحتمية. [ 3 ]

EXPTIME-complete

تُعتبر مسألة القرار كاملةً في مجموعة EXPTIME إذا كانت تنتمي إلى هذه المجموعة، وكان لكل مسألة في EXPTIME اختزالٌ متعدد الحدود إليها. بعبارة أخرى، توجد خوارزمية متعددة الحدود تُحوّل حالات إحدى المسألتين إلى حالات الأخرى بنفس الإجابة. يمكن اعتبار المسائل الكاملة في مجموعة EXPTIME أصعب المسائل في هذه المجموعة. تجدر الإشارة إلى أنه على الرغم من عدم معرفة ما إذا كانت NP تساوي P، إلا أننا نعلم أن المسائل الكاملة في مجموعة EXPTIME لا تنتمي إلى P؛ فقد ثبت، وفقًا لنظرية التسلسل الهرمي الزمني ، أنه لا يمكن حل هذه المسائل في وقت متعدد الحدود .

في نظرية الحوسبة ، تُعدّ مسألة التوقف إحدى المسائل الأساسية غير القابلة للحل : وهي تحديد ما إذا كانت آلة تورينغ الحتمية (DTM) ستتوقف أم لا. ومن أهم المسائل الأساسية في فئة EXPTIME-complete مسألة أبسط منها، وهي التي تسأل عما إذا كانت آلة تورينغ الحتمية ستتوقف عند مدخل مُعطى في k خطوة على الأكثر. تُصنّف هذه المسألة ضمن فئة EXPTIME لأن المحاكاة البسيطة تتطلب زمنًا قدره O( k )، ويتم ترميز المدخل k باستخدام O(log k ) بت، مما يؤدي إلى عدد أُسّي من عمليات المحاكاة. وهي تُصنّف ضمن فئة EXPTIME-complete لأنه، بشكل عام، يُمكننا استخدامها لتحديد ما إذا كانت الآلة التي تحل مسألة EXPTIME تقبل عددًا أُسّيًا من الخطوات؛ ولن تستخدم أكثر من ذلك. [ 4 ] وتُصنّف المسألة نفسها، مع كتابة عدد الخطوات بنظام العد الأحادي، ضمن فئة P-complete .

تشمل الأمثلة الأخرى للمسائل الكاملة وفقًا لمعيار EXPTIME مسألة تقييم وضعية في الشطرنج المعمم ، [ 5 ] والداما ، [ 6 ] أو لعبة غو (بقواعد كو اليابانية). [ 7 ] تتمتع هذه الألعاب باحتمالية أن تكون كاملة وفقًا لمعيار EXPTIME لأن مدة اللعبة قد تصل إلى عدد من النقلات يتناسب طرديًا مع حجم رقعة اللعب. في مثال لعبة غو، من المعروف أن قاعدة كو اليابانية تُشير إلى اكتمال اللعبة وفقًا لمعيار EXPTIME، ولكن من غير المعروف ما إذا كانت القواعد الأمريكية أو الصينية للعبة كاملة وفقًا لهذا المعيار (إذ قد تتراوح بين PSPACE وEXPSPACE).

في المقابل، غالباً ما تكون الألعاب المعممة التي يمكن أن تستمر لعدد من الحركات يكون متعدد الحدود بالنسبة لحجم اللوحة، ألعاباً كاملة من فئة PSPACE . وينطبق الأمر نفسه على الألعاب الطويلة أُسّياً التي يكون فيها عدم التكرار تلقائياً.

دوائر مختصرة

هناك مجموعة أخرى مهمة من المسائل الكاملة في إطار معيار EXPTIME تتعلق بالدوائر المختصرة. الفكرة هي أنه إذا استطعنا ضغط وصف مسألة تتطلب وقتًا متعدد الحدود بشكل أُسّي، فإن تلك المسألة المضغوطة ستتطلب وقتًا أُسّيًا.

على سبيل المثال، يمكن وصف بعض الرسوم البيانية بإيجاز بواسطة دائرة منطقية صغيرة. تحتوي هذه الدائرة على2ن{\displaystyle 2n}مدخلات، مخرج واحد وصoلy(ن){\displaystyle {\mathsf {poly}}(n)}البوابات، مما يستلزمصoلy(ن){\displaystyle {\mathsf {poly}}(n)}أجزاء لوصفها. تمثل الدائرة رسمًا بيانيًا مع2ن{\displaystyle 2^{n}}الرؤوس. لكل زوج من الرؤوس، إذا تم وضع الشفرة الثنائية للرأسين في الدائرة، فإن مخرج الدائرة يحدد ما إذا كان الرأسان متصلين بحافة.

بالنسبة للعديد من مسائل القرار الكاملة من النوع P التي تحدث بشكل طبيعي حول الرسوم البيانية، حيث يتم التعبير عن الرسم البياني بتمثيل طبيعي مثل مصفوفة التجاور ، فإن حل نفس المسألة على تمثيل دائرة موجزة يكون كاملاً من النوع EXPTIME، لأن المدخلات أصغر بشكل أسي؛ لكن هذا يتطلب برهانًا غير بديهي، لأن الدوائر الموجزة لا يمكنها وصف سوى فئة فرعية من الرسوم البيانية. [ 8 ]

بشكل عام، دائرة منطقية معن{\displaystyle n}المدخلات ومخرج واحد هو تمثيل موجز لسلسلة من2ن{\displaystyle 2^{n}}يمكن استخدام البتات لوصف كائن آخر، مثل الرسم البياني، أو صيغة 3-CNF ، وما إلى ذلك. بالنسبة لجميع مسائل NP-complete المعروفة تقريبًا، فإن النسخة المختصرة منها هي NEXP-complete. على وجه الخصوص، فإن SUCCINCT 3-SAT هي NEXP-complete في ظل اختزالات الوقت متعدد الحدود. [ 9 ] [ 10 ]

مراجع

  1. ↑ باباديميتريو، كريستوس (1994). التعقيد الحسابي . أديسون-ويسلي. ISBN 0-201-53082-1.القسم 20.1، الصفحة 491.
  2. ↑ جوريس هارتمانيس ، نيل إيمرمان ، فيفيان سيولسون. "المجموعات المتفرقة في NP − P: EXPTIME مقابل NEXPTIME". المعلومات والتحكم ، المجلد 65، العدد 2/3، الصفحات 158-181. 1985. في مكتبة ACM الرقمية
  3. ↑ باباديميتريو (1994 ، ص 495، القسم 20.1، النتيجة 3) 
  4. ↑ دو، دينغ-تشو؛ كو، كير-آي (2014)، نظرية التعقيد الحسابي ، سلسلة وايلي في الرياضيات المتقطعة والتحسين ( الطبعة الثانية)، جون وايلي وأولاده، الاقتراح 3.30، ISBN  9781118594971.
  5. ↑ فرانكل، أفيزري ؛ ليختنشتاين، ديفيد (1981). "حساب استراتيجية مثالية للشطرنج من الرتبة n × n يتطلب وقتًا أُسّيًا بالنسبة إلى n". مجلة نظرية التوافيق . السلسلة أ. 31 (2): 199-214 . doi : 10.1016/0097-3165(81)90016-9 .
  6. ↑ جيه إم روبسون (1984). "لعبة الداما من الرتبة N × N كاملة من حيث الوقت المقدر". مجلة SIAM للحوسبة . 13 (2): 252-267 . doi : 10.1137/0213018 .
  7. ↑ جيه إم روبسون (1983). "تعقيد لغة غو". معالجة المعلومات؛ وقائع مؤتمر الاتحاد الدولي لمعالجة المعلومات . الصفحات 413-417 . 
  8. ^ باباديميتريو (1994 ، ص. 495، القسم 20.1) 
  9. ↑ باباديميتريو، كريستوس هـ.؛ ياناكاكيس، ميهاليس (1986-12-01). "ملاحظة حول التمثيلات الموجزة للرسوم البيانية" . المعلومات والتحكم . 71 (3): 181-185 . doi : 10.1016/S0019-9958(86)80009-2 . ISSN 0019-9958 . 
  10. ↑ ويليامز، رايان (14 أكتوبر 2011). "مقال رأي: جولة سريعة حول حدود تعقيد الدوائر" . أخبار ACM SIGACT . 42 (3): 54-76 . doi : 10.1145/2034575.2034591 . ISSN 0163-5700 .