إكسب سبيس

في نظرية التعقيد الحسابي ، تُعرف مجموعة EXPSPACE بأنها مجموعة جميع مسائل القرار التي يمكن حلها بواسطة آلة تورينج حتمية في فضاء أسي ، أي في${\displaystyle O(2^{p(n)})}$الفضاء، حيث${\displaystyle p(n)}$هي دالة متعددة الحدود لـ${\displaystyle n}$بعض المؤلفين يقيدون${\displaystyle p(n)}$يُفترض أن تكون دالة خطية ، لكن معظم المؤلفين يُطلقون على الفئة الناتجة اسم ESPACE . إذا استخدمنا آلة غير حتمية بدلاً من ذلك، فسنحصل على الفئة NEXPSPACE ، والتي تُساوي EXPSPACE وفقًا لنظرية سافيتش .

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

تُعتبر مجموعة EXPSPACE مجموعة شاملة صارمة من مجموعات PSPACE و NP و P. وهي تحتوي على مجموعة EXPTIME ويُعتقد أنها تحتوي عليها بشكل صارم، ولكن هذا لم يتم إثباته.

فيما يتعلق بـ DSPACE و NSPACE ،

${\displaystyle {\mathsf {EXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}\left(2^{n^{k}}\right)=\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}\left(2^{n^{k}}\right)}$

• تعقيد اللعبة

• بيرمان، ليونارد (1 مايو 1980). "تعقيد النظريات المنطقية" . علوم الحاسوب النظرية . 11 (1): 71-77 . doi : 10.1016/0304-3975(80)90037-7 .
• مايكل سيبسر (1997). مقدمة في نظرية الحوسبة . دار نشر PWS. رقم ISBN 0-534-94728-X.القسم 9.1.1: اكتمال الفضاء الأسي، الصفحات  313-317 . يوضح أن تحديد تكافؤ التعبيرات النمطية مع الأسية هو أمر كامل في EXPSPACE.