EXPSPACE
کمپیوٹیشنل پیچیدگی کے نظریہ میں، تمام فیصلہ کن مسائل کا مجموعہ ہے جو ایک تعیناتی ٹورنگ مشین کے ذریعہ ایکسپونینشیل اسپیس میں حل کیا جاسکتا ہے، یعنی خلا میں، جہاں کا کثیر الجہتی فعل ہے۔ کچھ مصنفین لکیری فنکشن ہونے تک محدود ہیں، لیکن زیادہ تر مصنفین اس کے بجائے نتیجے میں آنے والی کلاس کو کہتے ہیں۔ اگر ہم اس کے بجائے ایک غیر متعین مشین استعمال کرتے ہیں، تو ہمیں کلاس ملتی ہے، جو سیوچ کے نظریہ کے برابر ہے۔ فیصلہ کرنے کا مسئلہ یہ ہے کہ اگر یہ اندر ہے، اور اندر کے ہر مسئلے میں کثیر الجہتی-وقت کئی-ایک کمی ہوتی ہے۔ دوسرے لفظوں میں، ایک کثیر الجہتی وقت کا الگورتھم ہے جو ایک ہی جواب کے ساتھ ایک کی مثالوں کو دوسرے کی مثالوں میں تبدیل کرتا ہے۔ مسائل کو سب سے مشکل مسائل سمجھا جا سکتا ہے۔ کا ایک سخت سپر سیٹ ہے، اور اور خیال کیا جاتا ہے کہ اس کا ایک سخت سپر سیٹ ہے۔ رسمی تعریف اور، مسائل کی مثالوں کے لحاظ سے کسی مسئلے کی ایک مثال یہ تسلیم کرنے کا مسئلہ ہے کہ آیا دو باقاعدہ تاثرات مختلف زبانوں کی نمائندگی کرتے ہیں، جہاں تاثرات چار آپریٹرز تک محدود ہیں: اتحاد، ہم آہنگی، کلین اسٹار (ایک اظہار کی صفر یا زیادہ کاپیاں)، اور مربع (ایک اظہار کی دو کاپیاں)۔ اگر کلین اسٹار کو چھوڑ دیا جاتا ہے، تو وہ مسئلہ بن جاتا ہے، جو اس طرح ہے، سوائے اس کے کہ اس کی تعریف تعیناتی کے بجائے غیر تعیناتی ٹورنگ مشینوں کے لحاظ سے کی گئی ہے۔ 1980 میں ایل برمن کی طرف سے یہ بھی دکھایا گیا ہے کہ حقیقی اعداد کے بارے میں کسی بھی پہلے درجے کے بیان کی تصدیق/غلط ثابت کرنے کا مسئلہ جس میں صرف اضافہ اور موازنہ (لیکن کوئی ضرب نہیں) شامل ہے۔ الور اور ہینزنگر نے وقت (عدد) کے ساتھ لکیری عارضی منطق کو بڑھایا اور ثابت کیا کہ ان کی منطق کا جواز مسئلہ EXPSPACE مکمل ہے۔ پیٹری نیٹ کے لیے احاطہ کا مسئلہ مکمل ہے۔ پیٹری جالوں کے لیے رسائ کا مسئلہ ایک طویل عرصے سے مشکل معلوم ہوتا تھا، لیکن غیر معمولی دکھایا گیا ہے، اس لیے شاید یہ اندر نہیں ہے۔ دوسرے طبقات کے ساتھ تعلق، اور کا ایک سخت سپر سیٹ جانا جاتا ہے۔ مزید شبہ ہے کہ یہ ایک سخت سپر سیٹ ہے، تاہم یہ معلوم نہیں ہے۔ گیم پیچیدگی حوالہ جات سیکشن 9.1.1: ایکسپونینشل اسپیس مکملتا، پی پی۔ 313-317 بھی دیکھیں۔ یہ ظاہر کرتا ہے کہ ایکسپوینٹیشن کے ساتھ باقاعدہ تاثرات کی مساوات کا تعین کرنا EXPSPACE مکمل ہے۔ پیچیدگی کلاسیں