EXPTIME

قسم تعقيد

مسألة P=NP

نظرية التعقيد الحسابي.

تعريف

وعلى صعيد آخر، أي مجموعة كل المسائل التي يمكن حلها في وقت محدود ب- حيث أن 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), مثل الشطرنج، ضامة,غو.

انظر كذلك

علاقات مع الاقسام الأخرى

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