Unique games conjecture
کمپیوٹیشنل پیچیدگی کے نظریہ میں، منفرد گیم قیاس (جسے اکثر یو جی سی کہا جاتا ہے) سبھاش کھوٹ نے 2002 میں بنایا تھا۔ قیاس یہ ہے کہ ایک مخصوص قسم کے کھیل کی تخمینہ قیمت کا تعین کرنے کا مسئلہ، جسے ایک منفرد کھیل کے نام سے جانا جاتا ہے، میں این پی ہارڈ کمپیوٹیشنل پیچیدگی ہوتی ہے۔ تخمینہ کی سختی کے نظریہ میں اس کے وسیع استعمال ہیں۔ اگر منفرد گیم کا قیاس درست ہے اور P ष्णپ ہے، تو بہت سے اہم مسائل کے لیے کثیر الجہتی وقت میں درست حل حاصل کرنا نہ صرف ناممکن ہے (جیسا کہ P بمقابلہ NP مسئلہ کی طرف سے پیش کیا گیا ہے)، بلکہ ایک اچھا کثیر الجہتی وقت کا تخمینہ حاصل کرنا بھی ناممکن ہے۔ جن مسائل کے لیے اس طرح کے غیر مطابقت پذیری کے نتیجے میں رکاوٹوں کے اطمینان کے مسائل شامل ہوں گے، جو مختلف شعبوں میں سامنے آتے ہیں۔ یہ قیاس اس لحاظ سے غیر معمولی ہے کہ تعلیمی دنیا تقریبا یکساں طور پر منقسم نظر آتی ہے کہ آیا یہ سچ ہے یا نہیں۔ فارمولیشن منفرد گیم قیاس آرائی کو کئی مساوی طریقوں سے بیان کیا جا سکتا ہے۔ منفرد لیبل کا احاطہ منفرد گیم قیاس کی درج ذیل تشکیل اکثر تخمینہ کی سختی میں استعمال ہوتی ہے۔ قیاس مندرجہ ذیل وعدے کے مسئلے کی این پی سختی کو پیش کرتا ہے جسے منفرد رکاوٹوں کے ساتھ لیبل کور کے نام سے جانا جاتا ہے۔ ہر کنارے کے لیے، دونوں چوٹیوں پر رنگ کچھ مخصوص ترتیب شدہ جوڑوں تک محدود ہیں۔ منفرد رکاوٹوں کا مطلب یہ ہے کہ ہر کنارے کے لیے کسی بھی ترتیب شدہ جوڑے کا رنگ ایک ہی نوڈ کے لیے ایک جیسا نہیں ہوتا۔ اس کا مطلب یہ ہے کہ سائز k کے حروف تہجی پر منفرد رکاوٹوں کے ساتھ لیبل کور کی ایک مثال کو ترتیبات کے مجموعے کے ساتھ ایک ہدایت شدہ گراف کے طور پر پیش کیا جا سکتا ہے πe: [k] → [k]، گراف کے ہر کنارے e کے لیے ایک۔ لیبل کور کی مثال کے لیے ایک تفویض G کے ہر ورٹیکس کو سیٹ [k] = {1,2,. k} میں ایک قدر دیتی ہے، جسے اکثر "رنگ" کہا جاتا ہے۔ اس طرح کی مثالیں اس معنی میں سختی سے محدود ہیں کہ ورٹیکس کا رنگ اپنے پڑوسیوں کے رنگوں کی منفرد وضاحت کرتا ہے، اور اس لیے اس کے پورے منسلک جزو کے لیے۔ اس طرح، اگر ان پٹ مثال ایک درست تفویض کو تسلیم کرتی ہے، تو اس طرح کی تفویض کو ایک ہی نوڈ کے تمام رنگوں پر دہرا کر مؤثر طریقے سے پایا جا سکتا ہے۔ خاص طور پر، یہ فیصلہ کرنے کا مسئلہ کہ آیا دی گئی مثال کسی تسلی بخش تفویض کو تسلیم کرتی ہے، کثیر الجہتی وقت میں حل کیا جا سکتا ہے۔ ایک منفرد لیبل کور مثال کی قیمت رکاوٹوں کا وہ حصہ ہے جسے کسی بھی تفویض سے پورا کیا جا سکتا ہے۔ تسلی بخش مثالوں کے لیے، یہ قدر 1 ہے اور اسے تلاش کرنا آسان ہے۔ دوسری طرف، غیر تسلی بخش کھیل کی قدر کا تعین کرنا بہت مشکل معلوم ہوتا ہے، یہاں تک کہ تقریبا. منفرد گیم قیاس اس مشکل کو باقاعدہ بناتا ہے۔ مزید رسمی طور پر، منفرد رکاوٹوں کے ساتھ (سی، ایس)-گیپ لیبل کور کا مسئلہ مندرجہ ذیل وعدے کا مسئلہ ہے (لائز، ایل این او): لائز = {جی: کچھ تفویض کم از کم جی میں رکاوٹوں کے سی-فریکشن کو مطمئن کرتی ہے} ایل این او = {جی: ہر تفویض زیادہ سے زیادہ جی میں رکاوٹوں کے ایس-فریکشن کو مطمئن کرتی ہے جہاں جی منفرد رکاوٹوں کے ساتھ لیبل کور کے مسئلے کی ایک مثال ہے۔ انوکھی گیم قیاس آرائی میں کہا گیا ہے کہ مستقل ε، δ> 0 کی ہر کافی چھوٹی جوڑی کے لیے، ایک مستقل k موجود ہے جیسے کہ (1 − δ، ε) سائز k کے حروف تہجی پر منفرد رکاوٹوں کے ساتھ-گیپ لیبل کور کا مسئلہ NP-سخت ہے۔ گراف کے بجائے، لیبل کور کے مسئلے کو لکیری مساوات کے لحاظ سے وضع کیا جا سکتا ہے۔ مثال کے طور پر، فرض کریں کہ ہمارے پاس انٹیجرز ماڈیولو 7 پر لکیری مساوات کا نظام ہے: یہ منفرد رکاوٹوں کے ساتھ لیبل کور کے مسئلے کی ایک مثال ہے۔ مثال کے طور پر، پہلی مساوات تعدد (1، 2) سے مطابقت رکھتی ہے جہاں (1، 2) (x1) = 2x2 ماڈیولو 7۔ دو پروور پروف سسٹم ایک منفرد گیم دو پروور ون راؤنڈ (2 پی 1 آر) گیم کا ایک خاص کیس ہے۔ دو پروور والے ایک راؤنڈ والے کھیل میں دو کھلاڑی (جسے پروور بھی کہا جاتا ہے) اور ایک ریفری ہوتا ہے۔ ریفری ہر کھلاڑی کو ایک معلوم امکان کی تقسیم سے تیار کردہ سوال بھیجتا ہے، اور ہر کھلاڑی کو جواب بھیجنا ہوتا ہے۔ جوابات مقررہ سائز کے ایک سیٹ سے آتے ہیں۔ کھیل کی وضاحت ایک پیش گوئی کے ذریعے کی جاتی ہے جو کھلاڑیوں کو بھیجے گئے سوالات اور ان کے فراہم کردہ جوابات پر منحصر ہوتی ہے۔ کھلاڑی پہلے سے ہی حکمت عملی کا فیصلہ کر سکتے ہیں، حالانکہ وہ کھیل کے دوران ایک دوسرے کے ساتھ بات چیت نہیں کر سکتے۔ کھلاڑی جیت جاتے ہیں اگر پیشن گوئی ان کے سوالات اور ان کے جوابات سے مطمئن ہو۔ دو ثبوت والے ایک راؤنڈ والے کھیل کو ایک منفرد کھیل کہا جاتا ہے اگر پہلے کھلاڑی کے ہر سوال اور ہر جواب کے لیے، دوسرے کھلاڑی کی طرف سے بالکل ایک جواب ہوتا ہے جس کے نتیجے میں کھلاڑی جیت جاتے ہیں، اور اس کے برعکس۔ کسی کھیل کی قدر تمام حکمت عملیوں پر کھلاڑیوں کے لیے جیتنے کا زیادہ سے زیادہ امکان ہے۔ انوکھے گیم قیاس میں کہا گیا ہے کہ مستقل ε، δ> 0 کی ہر کافی چھوٹی جوڑی کے لیے، ایک مستقل k موجود ہے کہ مندرجہ ذیل وعدہ مسئلہ (لائز، Lno) NP-سخت ہے: لائز = {G: G کی قیمت کم از کم 1 − δ} Lno = {G: G کی قیمت زیادہ سے زیادہ ε ہے جہاں G ایک انوکھا گیم ہے جس کے جوابات سائز k کے سیٹ سے آتے ہیں۔ ممکنہ طور پر قابل جانچ ثبوت متبادل طور پر، انوکھے گیم قیاس NP میں مسائل کے لیے ایک مخصوص قسم کے ممکنہ طور پر قابل جانچ ثبوت کے وجود کو پیش کرتا ہے۔ ایک منفرد کھیل کو استفسار کی پیچیدگی 2 کے ساتھ ایک خاص قسم کے غیر موافقت پذیر ممکنہ طور پر قابل جانچ ثبوت کے طور پر دیکھا جا سکتا ہے، جہاں تصدیق کنندہ کے ممکنہ سوالات کے ہر جوڑے اور پہلے استفسار کے ہر ممکنہ جواب کے لیے، دوسرے استفسار کا بالکل ایک ممکنہ جواب ہوتا ہے جو تصدیق کنندہ کو قبول کرتا ہے، اور اس کے برعکس۔ انوکھی گیم قیاس آرائی میں کہا گیا ہے کہ مستقلات کی ہر کافی چھوٹی جوڑی کے لیے ایک مستقل ایسا ہوتا ہے کہ این پی میں ہر مسئلے کے پاس مکمل، مستحکم اور بے ترتیب پیچیدگی کے ساتھ سائز کے حروف تہجی پر ممکنہ طور پر جانچنے کے قابل ثبوت ہوتا ہے جو کہ ایک منفرد کھیل ہے۔ مطابقت انوکھی گیم قیاس آرائی سبھاش کھوٹ نے 2002 میں متعارف کرائی تھی تاکہ اندازے کی سختی کے نظریہ میں بعض سوالات پر پیش رفت کی جا سکے۔ انوکھی گیم قیاس آرائی کی سچائی بہت سے معروف تخمینہ الگورتھم (فرض کرتے ہوئے P § NP) کی اصلاح کا اشارہ کرے گی۔ مثال کے طور پر، کسی گراف میں زیادہ سے زیادہ کٹوتی کا تخمینہ لگانے کے لیے گومینس اور ولیمسن کے الگورتھم کے ذریعے حاصل کردہ تخمینہ تناسب کسی بھی اضافی مستقل کے اندر بہترین ہوتا ہے، یہ فرض کرتے ہوئے کہ منفرد گیم قیاس اور پی ष्णپ۔ نتائج کی ایک فہرست جس کے بارے میں منفرد گیم قیاس آرائی کا مطلب معلوم ہوتا ہے، ملحقہ ٹیبل میں کمزور مفروضے P § NP کے لیے متعلقہ بہترین نتائج کے ساتھ دکھایا گیا ہے۔ ایک مستقل یا اس کا مطلب ہے کہ نتیجہ ہر مستقل (مسئلہ کے سائز کے حوالے سے) کے لیے بالترتیب اس سے زیادہ یا اس سے کم سختی سے برقرار رہتا ہے۔ بحث اور متبادل فی الحال، منفرد گیم قیاس آرائی کی سچائی کے بارے میں کوئی اتفاق رائے نہیں ہے۔ قیاس آرائی کی کچھ مضبوط شکلوں کی تردید کی گئی ہے۔ قیاس کی ایک مختلف شکل یہ پیش کرتی ہے کہ جب کسی منفرد کھیل کی قیمت کم از کم اس صورت سے مختلف ہوتی ہے جب قیمت زیادہ سے زیادہ ہوتی ہے تو کثیر الجہتی وقت کے الگورتھم کے لیے ناممکن ہے (لیکن شاید این پی ہارڈ نہیں)۔ قیاس کی یہ شکل اب بھی تخمینہ کی سختی میں ایپلی کیشنز کے لیے مفید ہوگی۔ قیاس کی مندرجہ بالا فارمولیشن میں مستقل ضروری ہے جب تک کہ P = NP نہ ہو۔ اگر انفرادیت کی ضرورت کو ہٹا دیا جائے تو متوازی تکرار تھیوریم کے ذریعہ متعلقہ بیان کو درست سمجھا جاتا ہے، یہاں تک کہ مارک کارپنسکی اور وارن شوڈی نے منفرد گیم کے مسئلے کی گھنے مثالوں کے لیے لکیری ٹائم ایکسپروکسیمیشن اسکیمیں بنائی ہیں۔ 2008 میں، پرساد راگھویندر نے دکھایا ہے کہ اگر منفرد گیم کا قیاس درست ہے، تو ہر رکاوٹ کے اطمینان کے مسئلے کے لیے بہترین تخمینہ تناسب ایک مخصوص سادہ سیمیڈفائنٹ پروگرامنگ مثال کے ذریعے دیا جاتا ہے، جو خاص طور پر کثیر الجہتی ہے۔ 2010 میں، پرساد راگھویندر اور ڈیوڈ اسٹیورر نے گیپ-سمال-سیٹ توسیع کے مسئلے کی وضاحت کی، اور اندازہ لگایا کہ یہ این پی-ہارڈ ہے۔ یہ قیاس منفرد گیم قیاس آرائی کو ظاہر کرتا ہے۔ یہ مکمل دو طرفہ ذیلی گراف تلاش کرنے کے لیے تخمینہ کے نتائج کی مضبوط سختی کو ثابت کرنے کے لیے بھی استعمال کیا گیا ہے۔ 2010 میں، سنجیو اروڑا، بواز باراک اور ڈیوڈ اسٹیورر نے منفرد گیم کے مسئلے کے لیے ایک سب ایکسپونینشیل ٹائم اپروکسیمیشن الگورتھم پایا۔ 2012 میں، یہ دکھایا گیا تھا کہ زیادہ سے زیادہ قیمت والی مثالوں کو کم از کم قیمت والی مثالوں سے ممتاز کرنا این پی-ہارڈ ہے۔ 2018 میں، کاغذات کی ایک سیریز کے بعد، قیاس آرائی کا ایک کمزور ورژن، جسے 2-2 گیمز کا قیاس کہا جاتا ہے، ثابت ہوا۔ ایک خاص معنوں میں، یہ اصل قیاس کے "نصف" کو ثابت کرتا ہے۔ یہ منفرد لیبل کور کے لیے سب سے مشہور فرق کو بھی بہتر بناتا ہے: کم از کم قیمت والی مثالوں سے زیادہ سے زیادہ قیمت والی مثالوں میں فرق کرنا این پی مشکل ہے۔ حوالہ جات نوٹ کریں۔ 2002 میں تخمینہ الگورتھم کی کمپیوٹنگ میں کمپیوٹیشنل پیچیدگی کا نظریہ کمپیوٹیشنل سختی کے مفروضے کمپیوٹر سائنس میں حل نہ ہونے والے مسائل قیاس آرائیاں