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)\geq {\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$ بيسبايس $\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), مثل الشطرنج، ضامة,غو.

انظر أيضا

• قسم تعقيد
• نظرية التعقيد الحسابي.
• مسألة P=NP
• خوارزمية