EXPTIME

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

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

تعريف[عدل]

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

  • أي مجموعة كل المسائل التي يمكن حلها في وقت محدود ب- حيث أن p هو كثير حدود .
  • حيث أن هي مجموعة كل المسائل التي يمكن تقريرها بواسطة آلة تورنج استبدالية حيث أن المساحة التي تستخدمها محدودة بكثير حدود. وهذا نابع من النظرية التالية :

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

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

P NP بيسبايس EXPTIME NEXPTIME EXPSPACE

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

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

أحد أهم النظريات هي ربط المسألة 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). "The complexity of Go". Information Processing; Proceedings of IFIP Congress. صفحات 413–417. 

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