PSPACE-complete
کمپیوٹیشنل پیچیدگی کے نظریہ میں، ایک فیصلہ مسئلہ پی ایس پی اے سی ای مکمل ہوتا ہے اگر اسے ان پٹ لمبائی (کثیر الجہتی جگہ) میں کثیر الجہتی میموری کی مقدار کا استعمال کرتے ہوئے حل کیا جاسکتا ہے اور اگر ہر دوسرے مسئلے کو کثیر الجہتی جگہ میں حل کیا جاسکتا ہے تو اسے کثیر الجہتی وقت میں اس میں تبدیل کیا جاسکتا ہے۔ پی ایس پی اے سی ای مکمل مسائل کو پی ایس پی اے سی ای میں سب سے مشکل مسائل کے طور پر سمجھا جا سکتا ہے، کثیر الجہتی جگہ میں حل ہونے والے فیصلہ سازی کے مسائل کی کلاس، کیونکہ اس طرح کے کسی بھی مسئلے کا حل پی ایس پی اے سی ای میں کسی بھی دوسرے مسئلے کو حل کرنے کے لیے آسانی سے استعمال کیا جا سکتا ہے۔ پی ایس پی اے سی ای مکمل ہونے والے مسائل میں باقاعدہ تاثرات اور سیاق و سباق کے حساس گرائمرز کی خصوصیات کا تعین، مقداری بولین فارمولوں کی سچائی کا تعین، مشترکہ اصلاح کے مسائل کے حل کے درمیان مرحلہ وار تبدیلیاں، اور بہت سی پہیلیاں اور کھیل شامل ہیں۔ نظریہ ایک مسئلہ کو پی ایس پی اے سی ای مکمل کے طور پر بیان کیا جاتا ہے اگر اسے میموری کی کثیر مقدار (یہ پی ایس پی اے سی ای سے تعلق رکھتا ہے) کا استعمال کرتے ہوئے حل کیا جا سکتا ہے اور پی ایس پی اے سی ای میں ہر مسئلہ کو کثیر الجہتی وقت میں دیئے گئے مسئلے کے مساوی مثال میں تبدیل کیا جا سکتا ہے۔ پی ایس پی اے سی ای مکمل مسائل کے زیادہ مشہور پیچیدگی کلاسز پی (کثیر الجہتی وقت) اور این پی (غیر متعین کثیر الجہتی وقت) سے باہر ہونے کا شبہ ہے، لیکن یہ معلوم نہیں ہے۔ یہ معلوم ہے کہ وہ کلاس این سی سے باہر ہیں، جو انتہائی موثر متوازی الگورتھم والے مسائل کی ایک کلاس ہے، کیونکہ این سی میں مسائل کو ان پٹ سائز کے لوگارتھم میں سپیس پولینومیل کی مقدار میں حل کیا جا سکتا ہے، اور اتنی کم مقدار میں حل ہونے والے مسائل کی کلاس سپیس ہیرارکی تھیوریم کے ذریعہ پی ایس پی اے سی ای میں سختی سے موجود ہے۔ وہ تبدیلیاں جن پر عام طور پر پی ایس پی اے سی ای-تکمیل کی وضاحت میں غور کیا جاتا ہے وہ کثیر الجہتی-وقت کئی-ایک کمی ہیں، وہ تبدیلیاں جو ایک قسم کے مسئلے کی ایک مثال کو مختلف قسم کے مسئلے کے مساوی واحد مثال میں لے جاتی ہیں۔ تاہم، ٹورنگ ریڈکشنز کا استعمال کرتے ہوئے تکمیل کی وضاحت کرنا بھی ممکن ہے، جس میں ایک مسئلہ کو دوسرے مسئلے کے لیے ذیلی روٹین پر کالوں کی کثیر تعداد میں حل کیا جا سکتا ہے۔ یہ معلوم نہیں ہے کہ آیا یہ دو قسم کی کمی پی ایس پی اے سی ای مکمل مسائل کی مختلف کلاسوں کا باعث بنتی ہیں۔ کمی کی دیگر اقسام، جیسے کئی ایک کمی جو ہمیشہ تبدیل شدہ ان پٹ کی لمبائی میں اضافہ کرتی ہیں، پر بھی غور کیا گیا ہے۔ پی ایس پی اے سی ای مکمل سیٹوں کے لیے برمن-ہارٹ مینس قیاس کے ایک ورژن میں کہا گیا ہے کہ اس طرح کے تمام سیٹ ایک جیسے نظر آتے ہیں، اس معنی میں کہ ان سب کو کثیر الجہتی وقت کے بائیجیکشن کے ذریعے ایک دوسرے میں تبدیل کیا جا سکتا ہے۔ رسمی زبانوں کی مثالیں ایک باقاعدہ اظہار دیا گیا ہے، اس بات کا تعین کرنا کہ آیا یہ اپنے حروف تہجی پر ہر سٹرنگ تیار کرتا ہے یا نہیں، پی ایس پی اے سی ای مکمل ہے۔ پہلا معروف پی ایس پی اے سی ای مکمل مسئلہ تعیناتی سیاق و سباق حساس گرائمرز کے لیے لفظ کا مسئلہ تھا۔ سیاق و سباق کے حساس گرائمرز کے لیے لفظ مسئلہ میں، کسی کو گرائمر کی تبدیلیوں کا ایک مجموعہ دیا جاتا ہے جو کسی جملے کی لمبائی کو بڑھا سکتا ہے، لیکن کم نہیں کر سکتا، اور اس بات کا تعین کرنا چاہتا ہے کہ آیا ان تبدیلیوں سے دیا گیا جملہ تیار کیا جا سکتا ہے۔ "ڈیٹرنیزم" کی تکنیکی حالت (جس کا مطلب یہ ہے کہ ہر تبدیلی سے یہ واضح ہوتا ہے کہ اسے استعمال کیا گیا تھا) اس بات کو یقینی بناتا ہے کہ اس عمل کو کثیر الجہتی جگہ میں حل کیا جاسکتا ہے، اور یہ ظاہر کرتا ہے کہ لکیری جگہ میں کمپیوٹیبل ہر (ممکنہ طور پر غیر تعیناتی) پروگرام کو سیاق و سباق کے حساس گرائمر کی تجزیہ میں تبدیل کیا جاسکتا ہے، اس طرح سے جو عزم کو محفوظ رکھتا ہے۔ 1970 میں، سیوچ کے نظریہ سے پتہ چلتا ہے کہ پی ایس پی اے سی ای غیر تعیین کے تحت بند ہے، جس کا مطلب یہ ہے کہ غیر متعین سیاق و سباق کے حساس گرائمر بھی پی ایس پی اے سی ای میں ہیں۔ منطق ایک معیاری پی ایس پی اے سی ای مکمل مسئلہ، جو پی ایس پی اے سی ای مکمل ہونے کے بہت سے دوسرے نتائج میں استعمال ہوتا ہے، مقداری بولین فارمولا کا مسئلہ ہے، جو بولین اطمینان بخش مسئلے کی عمومی شکل ہے۔ مقداری بولین فارمولا کا مسئلہ ایک بولین اظہار کو ان پٹ کے طور پر لیتا ہے، جس میں اس کے تمام متغیرات کو عالمی یا وجود کے لحاظ سے مقداری کیا جاتا ہے، مثال کے طور پر: مسئلہ کی پیداوار مقداری اظہار کی قدر ہے۔ اس قدر کو تلاش کرنا پی ایس پی اے سی ای مکمل ہے۔ ری کنفیگریشن ری کنفیگریشن کے مسائل ایک مشترکہ مسئلے کے حل کی ریاستی جگہ کے رابطے سے متعلق ہیں۔ مثال کے طور پر، یہ جانچنا کہ آیا گراف کے دو 4 رنگوں کو ایک دوسرے سے ایسی چالوں کے ذریعے جوڑا جا سکتا ہے جو ایک وقت میں ایک سرے کا رنگ بدلتی ہیں، ہر مرحلے پر ایک درست 4 رنگ کو برقرار رکھنا، پی ایس پی اے سی ای مکمل ہے، حالانکہ 3 رنگوں کے لیے ایک ہی مسئلہ کثیر الجہتی وقت میں حل کیا جا سکتا ہے۔ تشکیل نو کے مسائل کا ایک اور خاندان، جو اس علاقے میں بہت سے دوسرے مسائل کے پی ایس پی اے سی ای-مکمل ثبوت کی بنیاد کے طور پر مقداری بولین فارمولوں کے لیے اسی طرح استعمال ہوتا ہے، اس میں غیر متعین رکاوٹ منطق شامل ہوتی ہے، جس میں ریاستیں ایک رکاوٹ گراف کی سمت ہوتی ہیں جو کچھ رکاوٹوں کے تابع ہوتی ہیں کہ ہر سرے پر کتنے کناروں کو اندر کی طرف ہونا چاہیے، اور جس میں ریاست سے ریاست کی حرکتیں ایک کنارے کی سمت کو الٹ دیتی ہیں۔ پہیلیاں اور کھیل مقداری بولین فارمولے کے مسئلے کی تشریح دو کھلاڑیوں، ایک تصدیق کنندہ اور ایک جعل ساز کے ذریعے کھیل کے طور پر کی جا سکتی ہے۔ کھلاڑی ایسی حرکتیں کرتے ہیں جو مقداری متغیرات کے لیے اقدار کو پر کرتے ہیں، جس ترتیب میں وہ گھڑے ہوئے ہوتے ہیں، تصدیق کنندہ موجودہ مقداری متغیرات کو پر کرتا ہے اور غلط کنندہ عالمگیر مقداری متغیرات کو پر کرتا ہے۔ اگر بھرا ہوا فارمولا درست ہو جاتا ہے تو تصدیق کنندہ کھیل جیت جاتا ہے، اور بصورت دیگر غلط کنندہ جیت جاتا ہے۔ ایک مقداری فارمولا تب ہی درست ہوتا ہے جب تصدیق کنندہ کے پاس جیتنے کی حکمت عملی ہو۔ اسی طرح، بہت سے دوسرے مشترکہ کھیلوں کے فاتح یا ہارنے والے کا تعین کرنے کا مسئلہ پی ایس پی اے سی ای مکمل ثابت ہوتا ہے۔ ایسے کھیلوں کی مثالیں جو پی ایس پی اے سی ای سے مکمل ہیں (جب انہیں عام کیا جاتا ہے تاکہ انہیں بورڈ پر کھیلا جا سکے) گیمز ہیکس اور ریورسی ہیں۔ کچھ دوسرے عمومی کھیل، جیسے شطرنج، چیکرز (ڈرافٹ)، اور گو ایکسپٹیم مکمل ہیں کیونکہ دو کامل کھلاڑیوں کے درمیان کھیل بہت لمبا ہو سکتا ہے، اس لیے ان کے پی ایس پی اے سی ای میں ہونے کا امکان نہیں ہے۔ لیکن اگر چالوں کی تعداد پر پابند کثیر الجہتی نافذ کیا جائے تو وہ پی ایس پی اے سی ای مکمل ہو جائیں گے۔ کسی ایک کھلاڑی کے ذریعے کھیلے جانے والے پہیلیوں کا پی ایس پی اے سی ای مکمل ہونا بھی ممکن ہے۔ ان کی تشریح اکثر تشکیل نو کے مسائل کے طور پر کی جا سکتی ہے، اور اس میں سولٹیئر گیمز رش آور، ماہجنگ، ایٹومیکس اور سوکوبن، اور مکینیکل کمپیوٹر ٹورنگ ٹمبل شامل ہیں۔ پی ایس پی اے سی ای-تکمیل ان پٹ سائز کے فنکشن کے طور پر پیچیدگی پر مبنی ہے، اس حد میں جو پابند کے بغیر بڑھتی ہے۔ روایتی بورڈ پر شطرنج جیسے محدود تعداد میں پوزیشن والے پزل یا کھیل پی ایس پی اے سی ای مکمل نہیں ہو سکتے، کیونکہ انہیں بہت بڑی تلاش کی میز کا استعمال کرتے ہوئے مستقل وقت اور جگہ میں حل کیا جا سکتا ہے۔ ان کھیلوں کے پی ایس پی اے سی ای مکمل ورژن تیار کرنے کے لیے، ان میں اس طرح سے ترمیم کی جانی چاہیے جس سے ان کی پوزیشنوں کی تعداد غیر محدود ہو، جیسے کہ انہیں بورڈ پر کھیلنا۔ کچھ معاملات میں، جیسے شطرنج کے لیے، یہ توسیعات مصنوعی ہوتی ہیں۔ حوالہ جات مزید پڑھنے کی پیچیدگی کی کلاسیں