Generalized geography
کمپیوٹیشنل پیچیدگی کے نظریہ میں، عمومی جغرافیہ ایک معروف پی ایس پی اے سی ای مکمل مسئلہ ہے۔ جغرافیہ بچوں کا کھیل ہے، جہاں کھلاڑی باری باری دنیا میں کہیں سے بھی شہروں کے نام لیتے ہیں۔ منتخب کردہ ہر شہر کا آغاز اسی حرف سے ہونا چاہیے جو پچھلے شہر کے نام کو ختم کرتا ہے۔ تکرار کی اجازت نہیں ہے۔ کھیل ایک من مانی ابتدائی شہر سے شروع ہوتا ہے اور اس وقت ختم ہوتا ہے جب کوئی کھلاڑی ہار جاتا ہے کیونکہ وہ جاری رکھنے سے قاصر ہوتا ہے۔ گراف ماڈل کھیل کو دیکھنے کے لیے، ایک ہدایت شدہ گراف بنایا جا سکتا ہے جس کے نوڈس دنیا کے ہر شہر ہیں۔ نوڈ N1 سے نوڈ N2 میں ایک تیر شامل کیا جاتا ہے اگر اور صرف اس صورت میں جب سٹی لیبلنگ N2 اس حرف سے شروع ہوتا ہے جو سٹی لیبلنگ نوڈ N1 کا نام ختم کرتا ہے۔ دوسرے لفظوں میں، ہم ایک شہر سے دوسرے شہر میں تیر کھینچتے ہیں اگر پہلا کھیل کے قوانین کے مطابق دوسرے کی طرف لے جا سکتا ہے۔ ہدایت شدہ گراف میں ہر متبادل کنارے ہر کھلاڑی (دو کھلاڑیوں کے کھیل کے لیے) سے مطابقت رکھتا ہے۔ پہلا کھلاڑی جو راستہ بڑھانے میں ناکام رہتا ہے وہ ہار جاتا ہے۔ کھیل کی ایک مثال (مشی گن کے کچھ شہروں پر مشتمل) نیچے دی گئی شکل میں دکھائی گئی ہے۔ عمومی جغرافیہ (جی جی) کھیل میں، ہم شہر کے ناموں کے گراف کو صوابدیدی ہدایت شدہ گراف سے تبدیل کرتے ہیں۔ مندرجہ ذیل گراف عمومی جغرافیہ کے کھیل کی ایک مثال ہے۔ کھیل کھیلنا ہم پی 1 کو پہلے حرکت کرنے والے کھلاڑی کے طور پر اور پی 2 کو دوسرے حرکت کرنے والے کھلاڑی کے طور پر بیان کرتے ہیں اور نوڈس کو این 1 سے این این کا نام دیتے ہیں۔ مندرجہ بالا اعداد و شمار میں، P1 کی جیت کی حکمت عملی مندرجہ ذیل ہے: N1 صرف نوڈس N2 اور N3 پر پوائنٹ کرتا ہے۔ اس طرح پی 1 کی پہلی حرکت ان دو انتخاب میں سے ایک ہونی چاہیے۔ P1 N2 کا انتخاب کرتا ہے (اگر P1 N3 کا انتخاب کرتا ہے، تو P2 N9 کا انتخاب کرے گا کیونکہ یہ واحد آپشن ہے اور P1 ہار جائے گا)۔ اگلا P2 N4 کا انتخاب کرتا ہے کیونکہ یہ واحد باقی انتخاب ہے۔ پی 1 اب این 5 کا انتخاب کرتا ہے اور پی 2 بعد میں این 3 یا این 7 کا انتخاب کرتا ہے۔ پی 2 کے انتخاب سے قطع نظر، پی 1 این 9 کا انتخاب کرتا ہے اور پی 2 کے پاس کوئی باقی انتخاب نہیں ہے اور وہ کھیل ہار جاتا ہے۔ کمپیوٹیشنل پیچیدگی اس بات کا تعین کرنے کا مسئلہ کہ عمومی جغرافیہ کے کھیل میں کس کھلاڑی کی جیت کی حکمت عملی ہے، پی ایس پی اے سی ای مکمل ہے۔ عام جغرافیہ پی ایس پی اے سی ای میں ہے جی جی = {75 جی، بی۔ پی 1 کے پاس نوڈ بی سے شروع ہونے والے گراف جی پر کھیلے جانے والے عمومی جغرافیہ کے کھیل کے لیے جیتنے کی حکمت عملی ہے۔ یہ ظاہر کرنے کے لیے کہ جی جی bul پی ایس پی اے سی ای، ہم ایک کثیر-خلائی تکراری الگورتھم پیش کرتے ہیں جس سے یہ طے ہوتا ہے کہ کس کھلاڑی کی جیت کی حکمت عملی ہے۔ جی جی کی ایک مثال کو دیکھتے ہوئے، جہاں جی ایک ڈائریکٹڈ گراف ہے اور این اسٹارٹ نامزد اسٹارٹ نوڈ ہے، الگورتھم ایم مندرجہ ذیل طور پر آگے بڑھتا ہے: ایم پر (این اسٹارٹ، این اسٹارٹ): نوڈ این اسٹارٹ کی آؤٹ ڈگری کی پیمائش کریں۔ اگر یہ ڈگری 0 ہے، تو واپس جائیں، کیونکہ پہلے کھلاڑی کے لیے کوئی چال دستیاب نہیں ہے۔ این اسٹارٹ سے ایک کنارے تک پہنچنے کے قابل تمام نوڈس کی فہرست بنائیں: این 1، این 2،.، این آئی۔ جی 1 بنانے کے لیے جی سے این اسٹارٹ اور اس سے جڑے تمام کناروں کو ہٹا دیں۔ فہرست n1،.، ni میں موجود ہر نوڈ nj کے لیے، M کو کال کریں۔ اگر یہ تمام کالز واپسی قبول کرتی ہیں، تو اس سے کوئی فرق نہیں پڑتا کہ P1 کون سا فیصلہ کرتا ہے، P2 کے پاس جیتنے کی حکمت عملی ہے، لہذا واپسی کو مسترد کر دیں۔ بصورت دیگر (اگر کالز میں سے ایک واپسی مسترد ہو جاتی ہے) پی 1 کے پاس ایک انتخاب ہے جو پی 2 کے لیے کسی بھی کامیاب حکمت عملی سے انکار کر دے گا، لہذا واپسی قبول کریں۔ الگورتھم ایم واضح طور پر جی جی کا فیصلہ کرتا ہے۔ یہ پی ایس پی اے سی ای میں ہے کیونکہ استعمال ہونے والی واحد غیر واضح کثیر الجہتی کام کی جگہ ریکرشن اسٹیک میں ہے۔ ریکرشن اسٹیک کے ذریعہ استعمال ہونے والی جگہ کثیر الجہتی ہوتی ہے کیونکہ ریکرشن کی ہر سطح اسٹیک میں ایک نوڈ کا اضافہ کرتی ہے، اور زیادہ سے زیادہ n سطحوں پر ہوتی ہے، جہاں n G میں نوڈس کی تعداد ہے۔ یہ بنیادی طور پر ڈیپتھ فرسٹ سرچ کے مساوی ہے۔ عمومی جغرافیہ اسپیس-ہارڈ ہے مندرجہ ذیل ثبوت ڈیوڈ لکٹنسٹین اور مائیکل سیپسر کی وجہ سے ہے۔ جی جی کی پی ایس پی اے سی ای سختی کو قائم کرنے کے لیے، ہم کثیر الجہتی وقت (پی) میں فارمولی گیم کے مسئلے (جسے پی ایس پی اے سی ای ہارڈ کہا جاتا ہے) کو جی جی میں کم کر سکتے ہیں۔ مختصر طور پر، فارمولہ-گیم کے مسئلے کی ایک مثال ایک مقداری بولین فارمولہ φ = HEx1 βx2 HEx3. Qxk (si) پر مشتمل ہے جہاں Q یا تو HE یا β ہے۔ یہ کھیل دو کھلاڑیوں، پی اے اور پی کے ذریعے کھیلا جاتا ہے، جو لگاتار xi کے لیے اقدار کا انتخاب کرتے ہیں۔ پی ای کھیل جیت جاتا ہے اگر فارمولا si سچ ہو جاتا ہے، اور پی اے جیت جاتا ہے اگر si غلط ہو جاتا ہے۔ فارمولہ si کو مشترکہ عام شکل میں سمجھا جاتا ہے۔ اس ثبوت میں، ہم فرض کرتے ہیں کہ کوانٹیفایر کی فہرست کا آغاز اور اختتام سادگی کے لیے وجودی کوالیفائر، HE کے ساتھ ہوتا ہے۔ نوٹ کریں کہ کسی بھی اظہار کو ڈمی متغیرات کو شامل کرکے اس شکل میں تبدیل کیا جا سکتا ہے جو si میں ظاہر نہیں ہوتے ہیں۔ اوپر دکھائے گئے گراف کی طرح گراف G کی تعمیر کرکے، ہم دکھائیں گے کہ فارمولی گیم کی کسی بھی مثال کو عمومی جغرافیہ کی مثال تک کم کیا جا سکتا ہے، جہاں P1 کے لیے زیادہ سے زیادہ حکمت عملی پی کے برابر ہے، اور P2 کے لیے زیادہ سے زیادہ حکمت عملی پی کے برابر ہے۔ نوڈس کی بائیں عمودی زنجیر کو فارمولی گیم میں متغیرات کے لیے اقدار کے انتخاب کے طریقہ کار کی نقل کرنے کے لیے ڈیزائن کیا گیا ہے۔ ہیرے کی ہر ساخت ایک مقداری متغیر سے مطابقت رکھتی ہے۔ کھلاڑی باری باری ہر برانچنگ نوڈ پر راستوں کا فیصلہ کرتے ہیں۔ کیونکہ ہم نے فرض کیا کہ پہلا مقداری وجود ہوگا، P1 پہلے جاتا ہے، بائیں نوڈ کو منتخب کرتا ہے اگر x1 درست ہے اور دائیں نوڈ اگر x1 غلط ہے۔ اس کے بعد ہر کھلاڑی کو زبردستی موڑ لینا چاہیے، اور پھر P2 x2 کے لیے ایک قدر کا انتخاب کرتا ہے۔ یہ متبادل تفویض بائیں طرف نیچے جاری رہتی ہیں۔ دونوں کھلاڑیوں کے تمام ہیروں سے گزرنے کے بعد، یہ دوبارہ P1 کی باری ہے، کیونکہ ہم نے فرض کیا کہ آخری مقداری وجود ہے۔ پی 1 کے پاس گراف کے دائیں طرف کے راستے پر چلنے کے سوا کوئی چارہ نہیں ہے۔ پھر حرکت کرنے کی پی 2 کی باری ہے۔ جب کھیل گراف کے دائیں جانب پہنچ جاتا ہے، تو یہ فارمولا گیم میں کھیل کے اختتام سے ملتا جلتا ہوتا ہے۔ یاد رکھیں کہ فارمولہ گیم میں، پی جیتتا ہے اگر si سچ ہے، جبکہ پی جیتتا ہے اگر si غلط ہے۔ گراف کا دایاں رخ اس بات کی ضمانت دیتا ہے کہ پی 1 صرف اس صورت میں جیتتا ہے جب پی جیتتا ہے، اور پی 2 صرف اس صورت میں جیتتا ہے جب پی جیتتا ہے۔ پہلے ہم یہ دکھاتے ہیں کہ جب پی جیتتا ہے تو پی 2 ہمیشہ جیتتا ہے۔ اگر پا جیت جاتا ہے، تو si غلط ہے۔ اگر si غلط ہے، تو ایک غیر تسلی بخش شق موجود ہے۔ پی 2 جیتنے کے لیے ایک غیر تسلی بخش شق کا انتخاب کرے گا۔ پھر جب پی 1 کی باری آئے تو اسے پی 2 کے ذریعے منتخب کردہ اس شق میں ایک لفظی کا انتخاب کرنا چاہیے۔ چونکہ شق کے تمام لفظی الفاظ غلط ہیں، اس لیے وہ بائیں عمودی سلسلے میں پہلے دیکھے گئے نوڈس سے منسلک نہیں ہوتے ہیں۔ یہ P2 کو بائیں زنجیر کے ہیرے میں متعلقہ نوڈ کے کنکشن کی پیروی کرنے اور اسے منتخب کرنے کی اجازت دیتا ہے۔ تاہم، P1 اب کسی بھی ملحقہ نوڈس اور نقصانات کو منتخب کرنے سے قاصر ہے۔ اب ہم دکھاتے ہیں کہ جب پی جیتتا ہے تو پی 1 ہمیشہ جیتتا ہے۔ اگر پی جیت جاتا ہے، تو si سچ ہے۔ اگر si درست ہے، تو گراف کے دائیں طرف کی ہر شق ایک حقیقی لفظی پر مشتمل ہے۔ پی 2 کسی بھی شق کا انتخاب کر سکتا ہے۔ پھر P1 لفظی حق کا انتخاب کرتا ہے۔ اور چونکہ یہ درست ہے، بائیں عمودی نوڈ میں اس کا ملحقہ نوڈ پہلے ہی منتخب کیا جا چکا ہے، اس لیے پی 2 کے پاس بنانے اور کھونے کے لیے کوئی حرکت نہیں ہے۔ پلانر جنرلائزڈ جغرافیہ پی ایس پی اے سی ای مکمل ہے جنرلائزڈ جغرافیہ پی ایس پی اے سی ای مکمل ہے، یہاں تک کہ جب پلانر گراف پر کھیلا جائے۔ مندرجہ ذیل ثبوت تھیوریم 3 سے ہے۔ چونکہ پلانر جی جی جی جی کا ایک خاص معاملہ ہے، اور جی جی پی ایس پی ای سی ای میں ہے، اس لیے پلانر جی جی پی ایس پی ای میں ہے۔ یہ ظاہر کرنا باقی ہے کہ پلانر جی جی اسپیس ہارڈ ہے۔ یہ یہ دکھا کر ثابت کیا جا سکتا ہے کہ کس طرح ایک صوابدیدی گراف کو پلانر گراف میں تبدیل کیا جائے، اس طرح کہ اس گراف پر کھیلے جانے والے جی جی کے کھیل کا وہی نتیجہ ہوگا جو اصل گراف پر ہے۔ ایسا کرنے کے لیے، صرف اصل گراف کے تمام ایج کراسنگ کو ختم کرنا ضروری ہے۔ ہم گراف اس طرح کھینچتے ہیں کہ کوئی بھی تین کنارے ایک نقطہ پر ایک دوسرے کو نہیں کاٹتے، اور ایک ہی کھیل میں کراسنگ کناروں کا کوئی جوڑا استعمال نہیں کیا جا سکتا۔ یہ عام طور پر ممکن نہیں ہے، لیکن فارمولہ گیم کی مثال سے بنائے گئے گراف کے لیے ہمیشہ ممکن ہے ؛ مثال کے طور پر ہمارے پاس کراسنگ میں شامل شق عمودی کے صرف کنارے ہو سکتے ہیں۔ اب ہم ہر کراسنگ کو اس تعمیر سے تبدیل کرتے ہیں: نتیجہ ایک پلانر گراف ہے، اور وہی کھلاڑی اصل گراف کی طرح جیت پر مجبور کر سکتا ہے: اگر کوئی کھلاڑی تبدیل شدہ کھیل میں V سے "اوپر" جانے کا انتخاب کرتا ہے، تو دونوں کھلاڑیوں کو "اوپر" سے W کی طرف بڑھنا جاری رکھنا چاہیے یا فوری طور پر ہار جانا چاہیے۔ لہذا تبدیل شدہ گیم میں V سے "اوپر" منتقل ہونا اصل گیم میں V → W حرکت کی تقلید کرتا ہے۔ اگر V → W ایک جیتنے والا اقدام ہے، تو تبدیل شدہ کھیل میں V سے "اوپر" جانا بھی ایک جیتنے والا اقدام ہے، اور اس کے برعکس۔ اس طرح، تبدیل شدہ گراف پر کھیلے جانے والے جی جی کے کھیل کا وہی نتیجہ ہوگا جو اصل گراف پر ہے۔ اس تبدیلی میں وقت لگتا ہے جو اصل گراف میں کنارے کے چوراہوں کی تعداد کا ایک مستقل ضرب ہے، اس طرح اس میں کثیر الجہتی وقت لگتا ہے۔ اس طرح پلانر جی جی پی ایس پی ای سی ای مکمل ہے۔ زیادہ سے زیادہ ڈگری 3 کے ساتھ پلانر دو طرفہ گراف پر کھیلے جانے والے زیادہ سے زیادہ ڈگری 3 جی جی کے ساتھ پلانر دو طرفہ گراف اب بھی پی ایس پی اے سی ای مکمل ہے، جس میں 3 سے زیادہ ڈگری کے عمودی حصوں کو زیادہ سے زیادہ ڈگری 3 کے ساتھ عمودی سلسلے سے تبدیل کیا جاتا ہے۔ ثبوت اندر ہے۔ اور مندرجہ ذیل تعمیر کا استعمال کرتا ہے: اگر ایک کھلاڑی اس تعمیر کے کسی بھی دروازے کا استعمال کرتا ہے، تو دوسرا کھلاڑی انتخاب کرتا ہے کہ کون سا اخراج استعمال کیا جائے گا۔ اس کے علاوہ تعمیر کو صرف ایک بار عبور کیا جا سکتا ہے، کیونکہ مرکزی سرے پر ہمیشہ جانا جاتا ہے۔ لہذا یہ تعمیر اصل سرے کے برابر ہے۔ کنارے کا جغرافیہ جی جی کی ایک قسم کو کنارے کا جغرافیہ کہا جاتا ہے، جہاں ہر حرکت کے بعد کھلاڑی جس کنارے سے گزرا اسے مٹا دیا جاتا ہے۔ یہ اصل جی جی کے برعکس ہے، جہاں ہر حرکت کے بعد کھلاڑی جس سرے پر ہوتا تھا اسے مٹا دیا جاتا ہے۔ اس نقطہ نظر میں، اصل جی جی کو ورٹیکس جغرافیہ کہا جا سکتا ہے۔ کنارے کا جغرافیہ پی ایس پی اے سی ای مکمل ہے۔ یہ ثابت کیا جا سکتا ہے کہ اسی تعمیر کا استعمال کیا گیا جو ورٹیکس جغرافیہ کے لیے استعمال کیا گیا تھا۔ غیر ہدایت شدہ جغرافیہ کسی غیر ہدایت شدہ گراف پر جغرافیہ کا کھیل کھیلنے پر بھی غور کیا جا سکتا ہے (یعنی کناروں کو دونوں سمتوں میں عبور کیا جا سکتا ہے)۔ فرینکل، شینر مین، اور المین سے پتہ چلتا ہے کہ غیر ہدایت شدہ ورٹیکس جغرافیہ کو کثیر الجہتی وقت میں حل کیا جا سکتا ہے، جبکہ غیر ہدایت شدہ کنارے کا جغرافیہ پی ایس پی اے سی ای مکمل ہے، یہاں تک کہ زیادہ سے زیادہ ڈگری 3 والے پلانر گراف کے لیے بھی۔ اگر گراف دو طرفہ ہے، تو غیر ہدایت شدہ ایج جغرافیہ کثیر الجہتی وقت میں حل کرنے کے قابل ہے۔ نتائج یہ دیکھتے ہوئے کہ جی جی پی ایس پی اے سی ای مکمل ہے، جی جی میں زیادہ سے زیادہ کھیل کے لیے کوئی کثیر الجہتی ٹائم الگورتھم موجود نہیں ہے جب تک کہ پی = پی ایس پی اے سی ای نہ ہو۔ تاہم، دوسرے کھیلوں کی پیچیدگی کو ثابت کرنا اتنا آسان نہیں ہو سکتا کیونکہ بعض کھیلوں (جیسے شطرنج) میں گیم پوزیشنوں کی ایک محدود تعداد ہوتی ہے-جس سے پی ایس پی اے سی ای مکمل مسئلے کی نقشہ سازی کرنا مشکل (یا ناممکن) ہو جاتا ہے۔ اس کے باوجود، بعض کھیلوں کی پیچیدگی کا تجزیہ اب بھی عمومی کاری کے ذریعے کیا جا سکتا ہے (مثال کے طور پر، ایک n × n بورڈ پر)۔ جی جی کی مکملتا کے ثبوت کے نتیجے کے طور پر، عمومی گو کے ثبوت کے لیے حوالہ جات دیکھیں۔ حوالہ جات مائیکل سیپسر، کمپیوٹیشن کے نظریہ کا تعارف، پی ڈبلیو ایس، 1997۔ PSPACE-مکمل مسائل