Valiant–Vazirani theorem
ویلینٹ-وزیرانی تھیوریم کمپیوٹیشنل پیچیدگی کے نظریہ میں ایک تھیوریم ہے جس میں کہا گیا ہے کہ اگر غیر متزلزل-SAT کے لیے کثیر الجہتی ٹائم الگورتھم ہے، تو NP = RP۔ یہ لیسلی ویلینٹ اور وجے وزیرانی نے اپنے مقالے میں ثابت کیا تھا جس کا عنوان این پی اتنا ہی آسان ہے جتنا کہ 1986 میں شائع ہونے والے منفرد حل کا پتہ لگانا۔ ثبوت ملمولی-وزیرانی-وزیرانی آئسولیشن لیما پر مبنی ہے، جسے بعد میں نظریاتی کمپیوٹر سائنس میں متعدد اہم ایپلی کیشنز کے لیے استعمال کیا گیا۔ ویلینٹ-وزیرانی تھیوریم کا مطلب ہے کہ بولین اطمینان بخش مسئلہ، جو کہ این پی مکمل ہے، کمپیوٹیشنل طور پر ایک مشکل مسئلہ بنا ہوا ہے یہاں تک کہ اگر ان پٹ مثالوں میں زیادہ سے زیادہ ایک تسلی بخش تفویض کا وعدہ کیا گیا ہو۔ ثبوت کا خاکہ غیر واضح-ایس اے ٹی یہ فیصلہ کرنے کا وعدہ مسئلہ ہے کہ آیا دیا گیا بولین فارمولا جس میں زیادہ سے زیادہ ایک تسلی بخش تفویض ہے وہ غیر تسلی بخش ہے یا بالکل ایک اطمینان بخش تفویض ہے۔ پہلی صورت میں، غیر متزلزل-SAT کے لیے ایک الگورتھم کو مسترد کرنا چاہیے، اور دوسری صورت میں اسے فارمولہ قبول کرنا چاہیے۔ اگر فارمولے میں ایک سے زیادہ تسلی بخش تفویض ہے، تو الگورتھم کے رویے پر کوئی شرط نہیں ہے۔ وعدے کا مسئلہ غیر متزلزل-SAT کا فیصلہ ایک غیر متعین ٹورنگ مشین کے ذریعے کیا جا سکتا ہے جس میں زیادہ سے زیادہ ایک قبول شدہ کمپیوٹیشن کا راستہ ہوتا ہے۔ اس لحاظ سے، یہ وعدہ مسئلہ پیچیدگی کلاس یو پی سے تعلق رکھتا ہے (جو عام طور پر صرف زبانوں کے لیے بیان کیا جاتا ہے)۔ ویلینٹ-وزیرانی تھیوریم کا ثبوت ایس اے ٹی سے ایس اے ٹی میں ممکنہ کمی پر مشتمل ہے کہ، کم از کم امکان کے ساتھ، آؤٹ پٹ فارمولا میں زیادہ سے زیادہ ایک تسلی بخش تفویض ہوتی ہے، اور اس طرح غیر واضح-ایس اے ٹی مسئلے کے وعدے کو پورا کرتا ہے۔ مزید واضح طور پر، کمی ایک بے ترتیب کثیر الجہتی وقت کا الگورتھم ہے جو بولین فارمولے کے متغیرات کے ساتھ بولین فارمولے کا نقشہ اس طرح بناتا ہے کہ ہر تسلی بخش تفویض بھی مطمئن ہو، اور اگر تسلی بخش ہو، تو کم از کم امکان کے ساتھ، ایک منفرد اطمینان بخش تفویض ہوتی ہے۔ کمی کو کثیر تعداد میں بار بار چلانے سے، ہر بار تازہ آزاد بے ترتیب بٹس کے ساتھ، ہمیں فارمولے ملتے ہیں۔ انتخاب کرتے ہوئے، ہمیں یہ امکان ملتا ہے کہ کم از کم ایک فارمولا منفرد طور پر تسلی بخش ہے، کم از کم اگر تسلی بخش ہو۔ یہ ٹورنگ کو ایس اے ٹی سے غیر متزلزل-ایس اے ٹی میں کمی دیتا ہے کیونکہ اس پر غیر متزلزل-ایس اے ٹی کے لیے ایک فرض شدہ الگورتھم کو استعمال کیا جا سکتا ہے۔ پھر ایس اے ٹی کی خود تخفیف کو ایک تسلی بخش تفویض کا حساب لگانے کے لیے استعمال کیا جا سکتا ہے، اگر یہ موجود ہو۔ مجموعی طور پر، یہ ثابت کرتا ہے کہ NP = RP اگر غیر واضح-SAT کو RP میں حل کیا جا سکتا ہے۔ کمی کا خیال فارمولے کے حل کی جگہ کو بے ترتیب افائن ہائپرپلین کے ساتھ کاٹنا ہے، جہاں بے ترتیب طور پر یکساں طور پر منتخب کیا جاتا ہے۔ ایک متبادل ثبوت ملمولی، وزیرانی اور وزیرانی کے الگ تھلگ لیما پر مبنی ہے۔ وہ ایک زیادہ عام ترتیب پر غور کرتے ہیں، اور یہاں کی ترتیب پر لاگو ہوتے ہیں اس سے صرف ایک الگ تھلگ ہونے کا امکان ملتا ہے۔ ساختی پیچیدگی کا نظریہ کمپیوٹیشنل پیچیدگی کے نظریہ میں نظریات