EXPTIME

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث

في نظرية التعقيد EXPTIME او EXP للاختصار هي مجموعة مسائل التي يمكن حلها بوقت أُسي بواسطة آلة تورنج حتمية .

تعريف[عدل]

يمكن تعريف هذا الصنف او القسم بعدة طرق :

  • \mbox{EXP}=\cup_{k>0} DTIME(2^{n^k}) اي مجموعة كل المسائل التي يمكن حلها في وقت محدود ب- 2^{p(n)} حيث أن p هو كثير حدود .
  • \mbox{EXP}=\mbox{APSPACE} حيث أن \mbox{APSPACE} هي مجموعة كل المسائل التي يمكن تقريرها بواسطة آلة تورنج استبدالية حيث ان المساحة التي تستخدمها محدودة بكثير حدود . وهذا نابع من النظرية التالية :
\forall s(n)\ge \mbox{log(n)} , \mbox{ASPACE(s(n))} = \cup_{c>0}DTIME(2^{c\cdot s(n)})

علاقات مع الاقسام الاخرى[عدل]

EXP يحوي كثير من الاقسام المعروفة وذلك للقدرة الهائلة الممنوحة له كما في التعريف حيث أنَّه يحوي القسمين NP و- PSPACE ولكن غير معروف اذا ما الاتجاه الاخر صحيح . اما عن علاقته مع القسم P فهي قد حسمت بواسطة نظرية الوقت الهرمية التي منها ينبع أنَّ  P \subsetneq EXP . كما انه بديهيا يتحقق التالي :

P \subseteq NP \subseteq PSPACE \subseteq EXPTIME \subseteq NEXPTIME \subseteq EXPSPACE

من نظريات الوقت والمساحة الهرمية يتحقق التالي :

  • PSPACE \subsetneq EXPSPACE
  •  NP\subsetneq NEXPTIME

لذا فان أحد الاحتواءات الثلاث الاولى يجب ان تكون احتواء فعلي وكذا للثلاث الاخيرات . كما انَّ رأي معظم علماء الحاسوب يميل إلى انَّ كل هذه الاحتواءات فعلية.

أحد أهم النظريات هي ربط المسألة EXP=NEXP بالمسألة الشهيرة NP=P , حيث أنه اذا NP=P حينها EXP=NEXP لاحظ ان العكس ليس بالضرورة صحيح إذ انه يمكن ان يكون NP≠P ولكن NEXP=EXP إذ انه يوجد اوراكل حيث أنه NP≠P ولكن NEXP=EXP , وبالضرورة يتحقق EXP≠NEXP اذا وفقط اذا يوجد لغة احادية (او مسألة احادية) التي هي في NP ولكن ليست في P . وغير معروف اذا ما يوجد لغة كهذه في NP ولكن ليست في P ( ولربما أيضا من الصعب ايجاد واحدة كهذه) .

مسائل كاملة[عدل]

مسألة,L, في EXP نقول انها في EXP-complete اذا لكل مسألة في EXP يمكن اختصارها إلى هذه المسألة . هذه المسائل لا يمكن ان تتبع القسم P وذلك لو انها تبعته فانه سيتحقق P=EXP وهذا غير صحيح لانه يناقض نظرية الوقت الهرمية .

أحد المسائل التي هي EXP كاملة هي مسألة التوقف المحدود , وهي المسألة : باعطائنا آلة تورنج حتمية M ,سلسلة x , وعدد صحيح n>0 وهو مكتوب بالنظام الثنائي . حدد اذا ما (M(x سوف تتوقف خلال n خطوات حسابية . هذه المسألة , اذا كان n معطى بالنظام الاحادي حينها المسألة هي P كاملة .

امثلة اخرى من ضمنها حساب الخطوة القادمة في العاب مُعممة (اي ان اللوح ابعاده ليست 8x8 انما nxn ), مثل الشطرنج [1] , ضامة[2],غو[3] .

مصادر[عدل]

  1. ^ Aviezri Fraenkel and D. Lichtenstein (1981). "Computing a perfect strategy for n×n chess requires time exponential in n". J. Comb. Th. A (31): 199–214. 
  2. ^ J. M. Robson (1984). "N by N checkers is Exptime complete". SIAM Journal on Computing 13 (2): 252–267. doi:10.1137/0213018. 
  3. ^ J. M. Robson (1983). Information Processing; Proceedings of IFIP Congress. صفحات 413–417. 

انظر أيضا[عدل]