PCP theorem
کمپیوٹیشنل پیچیدگی کے نظریہ میں، پی سی پی تھیوریم (جسے پی سی پی کیریکٹرائزیشن تھیوریم بھی کہا جاتا ہے) بیان کرتا ہے کہ این پی پیچیدگی کی کلاس میں ہر فیصلے کے مسئلے میں مستقل استفسار کی پیچیدگی اور لوگرتھمک بے ترتیب پیچیدگی (بے ترتیب بٹس کا لوگرتھمک نمبر استعمال کرتا ہے) کے ممکنہ طور پر قابل جانچ ثبوت (ایسے ثبوت جن کی بے ترتیب الگورتھم کے ذریعے جانچ کی جا سکتی ہے) ہوتے ہیں۔ پی سی پی تھیوریم کا کہنا ہے کہ کچھ عالمگیر مستقل K کے لیے، ہر n کے لیے، لمبائی n کے بیان کے لیے کسی بھی ریاضیاتی ثبوت کو لمبائی پولی (n) کے مختلف ثبوت کے طور پر دوبارہ لکھا جا سکتا ہے جو کہ ایک بے ترتیب الگورتھم کے ذریعے 99 فیصد درستگی کے ساتھ باضابطہ طور پر قابل تصدیق ہے جو اس ثبوت کے صرف K حروف کا معائنہ کرتا ہے۔ پی سی پی تھیوریم تخمینہ کی کمپیوٹیشنل سختی کے نظریہ کی بنیاد ہے، جو اصلاح کے مختلف مسائل کے لیے موثر تخمینہ الگورتھم کو ڈیزائن کرنے میں موروثی مشکل کی تحقیقات کرتا ہے۔ انگو ویگنر نے اسے "کک کے نظریہ کے بعد سے پیچیدگی کے نظریہ کا سب سے اہم نتیجہ" اور اوڈیڈ گولڈریچ نے "اختراعی خیالات سے بھرپور متاثر کن کاموں کے سلسلے کا اختتام" کے طور پر بیان کیا ہے۔ رسمی بیان پی سی پی تھیوریم بیان کرتا ہے کہ این پی = پی سی پی [او (لاگ این)، او (1)]، جہاں پی سی پی [آر (این)، کیو (این)] مسائل کی وہ کلاس ہے جس کے لیے کسی حل کا ممکنہ طور پر قابل جانچ ثبوت دیا جا سکتا ہے، اس طرح کہ ثبوت کو بے ترتیب کے آر (این) بٹس کا استعمال کرتے ہوئے کثیر الجہتی وقت میں چیک کیا جا سکتا ہے اور ثبوت کے کیو (این) بٹس کو پڑھ کر، درست ثبوت ہمیشہ قبول کیے جاتے ہیں، اور غلط ثبوت کو کم از کم 1/2 امکان کے ساتھ مسترد کر دیا جاتا ہے۔ n کسی مسئلے کی مثال کی تفصیل کی بٹس میں لمبائی ہے۔ مزید نوٹ کریں کہ تصدیق کا الگورتھم غیر موافقت پذیر ہے: جانچنے کے لیے ثبوت کے بٹس کا انتخاب صرف بے ترتیب بٹس اور مسئلہ کی مثال کی تفصیل پر منحصر ہوتا ہے، ثبوت کے اصل بٹس پر نہیں۔ پی سی پی اور تخمینہ کی سختی پی سی پی تھیوریم کی ایک متبادل تشکیل میں کہا گیا ہے کہ رکاوٹ اطمینان کے مسئلے کی تسلی بخش رکاوٹوں کا زیادہ سے زیادہ حصہ کسی مستقل عنصر کے اندر این پی-ہارڈ سے لگ بھگ ہوتا ہے۔ رسمی طور پر، کچھ مستقلات q اور α <1 کے لیے، مندرجہ ذیل وعدے کا مسئلہ (لائز، Lno) ایک NP-سخت فیصلہ کا مسئلہ ہے: لائز = {φ: میں موجود تمام رکاوٹیں بیک وقت تسلی بخش ہیں} Lno = {φ: ہر تفویض φ کی رکاوٹوں کے α حصے سے کم کو مطمئن کرتی ہے، جہاں φ بولین حروف تہجی پر زیادہ سے زیادہ q متغیر فی رکاوٹ کے ساتھ ایک رکاوٹ اطمینان کا مسئلہ (CSP) ہے۔ اوپر بیان کردہ کلاس پی سی پی سے تعلق یہ دیکھ کر دیکھا جا سکتا ہے کہ ثبوت میں بٹس q کی مستقل تعداد کی جانچ کو ثبوت کے ان بٹس پر q بولین متغیرات میں رکاوٹ کا اندازہ لگانے کے طور پر دیکھا جا سکتا ہے۔ چونکہ تصدیق الگورتھم بے ترتیب کے O (log n) بٹس کا استعمال کرتا ہے، اس لیے اسے CSP کے طور پر پیش کیا جا سکتا ہے جیسا کہ اوپر پولی (n) رکاوٹوں کے ساتھ بیان کیا گیا ہے۔ پی سی پی تھیوریم کی دوسری خصوصیت پھر α = 1/2 کے ساتھ وعدے کی شرط کی ضمانت دیتی ہے: اگر این پی مسئلے کا جواب ہاں میں ہے، تو ہر رکاوٹ (جو بے ترتیب بٹس کے لیے کسی خاص قدر سے مطابقت رکھتی ہے) کی ایک تسلی بخش تفویض ہوتی ہے (ایک قابل قبول ثبوت) ؛ بصورت دیگر، کسی بھی ثبوت کو کم از کم 1/2 امکان کے ساتھ مسترد کیا جانا چاہیے، جس کا مطلب ہے کہ کسی بھی تفویض کو 1/2 سے کم رکاوٹوں کو پورا کرنا چاہیے (جس کا مطلب ہے کہ اسے 1/2 سے کم امکان کے ساتھ قبول کیا جائے گا)۔ لہذا، وعدے کے مسئلے کے لیے ایک الگورتھم بنیادی این پی مسئلے کو حل کرنے کے قابل ہوگا، اور اس لیے وعدے کا مسئلہ این پی سخت ہونا چاہیے۔ اس نظریہ کے نتیجے میں، یہ دکھایا جا سکتا ہے کہ قدرتی اصلاح کے بہت سے مسائل کے حل بشمول زیادہ سے زیادہ بولین فارمولہ اطمینان بخش، گراف میں زیادہ سے زیادہ آزاد سیٹ، اور جالی کے لیے مختصر ترین ویکٹر مسئلہ کا مؤثر طریقے سے تخمینہ نہیں لگایا جا سکتا جب تک کہ P = NP نہ ہو۔ یہ اس طرح کے مسائل کے حل کو مذکورہ بالا فارم کے وعدے کے مسئلے کے قریب کرنے کے مسئلے کو کم کرکے کیا جا سکتا ہے۔ ان نتائج کو بعض اوقات پی سی پی تھیوریم بھی کہا جاتا ہے کیونکہ انہیں کچھ اضافی ڈھانچے کے ساتھ این پی کے لیے ممکنہ طور پر قابل جانچ ثبوت کے طور پر دیکھا جا سکتا ہے۔ ثبوت کمزور نتیجہ کا ثبوت، این پی پی سی پی [این 3، 1] ڈیکسٹر کوزین کے ایک لیکچر میں دیا گیا ہے۔ پی سی پی تھیوریم انٹرایکٹو ثبوتوں اور ممکنہ طور پر قابل جانچ ثبوتوں پر کام کی ایک لمبی لائن کا اختتام ہے۔ معیاری ثبوتوں اور ممکنہ طور پر قابل جانچ ثبوتوں سے متعلق پہلا نظریہ یہ بیان ہے کہ NEXP ष् پی سی پی [پولی (این)، پولی (این)] کے ذریعے ثابت کیا گیا ہے۔ ابتدائی حروف کی ابتدا پی سی پی سی (این)، ایس (این) [آر (این)، کیو (این)] کی وضاحت ممکنہ طور پر قابل جانچ ثبوت پر کی گئی ہے۔ نوٹیشن ایک فنکشن کی ہوتی ہے جو ایک مخصوص پیچیدگی کلاس کو واپس کرتی ہے۔ اوپر بیان کردہ وضاحت دیکھیں۔ اس تھیوریم کا نام ("پی سی پی تھیوریم") شاید یا تو "پی سی پی" سے آتا ہے جس کا مطلب ہے "ممکنہ طور پر قابل جانچ ثبوت"، یا اوپر بیان کردہ اشارے (یا دونوں) سے آتا ہے۔ پہلا نظریہ [1990 میں] اس کے بعد، اس کام میں استعمال ہونے والے طریقوں کو بابائی، لانس فورٹنو، لیون، اور زیگیڈی نے 1991 میں، فیج، گولڈ واسر، لنڈ، سفرا، اور زیگیڈی (1991)، اور اروڑا اور سفرا نے 1992 میں بڑھایا تاکہ 1998 میں اروڑا، لنڈ، موٹوانی، سوڈان، اور زیگیڈی کے ذریعہ پی سی پی تھیوریم کا ثبوت فراہم کیا جا سکے۔ 2001 کا گوڈل انعام سنجیو اروڑا، اوریئل فیج، شافی گولڈ واسر، کارسٹن لنڈ، لاسزلو لووز، راجیو موٹوانی، سموئیل سفرا، مدھو سوڈان، اور ماریو زیگیڈی کو پی سی پی تھیوریم اور اس کے قریب قریب کی سختی سے تعلق پر کام کرنے کے لیے دیا گیا تھا۔ 2005 میں اریٹ دینور نے ایکسپینڈر گراف کا استعمال کرتے ہوئے پی سی پی تھیوریم کا ایک نمایاں طور پر آسان ثبوت دریافت کیا۔ اس کے لیے انہیں 2019 کا گوڈل انعام ملا۔ کوانٹم اینالاگ 2012 میں، تھامس ویڈک اور سویوشی ایٹو نے ایک نتیجہ شائع کیا جس میں "ملٹی پلیئر گیم میں الجھے ہوئے پروورز کی مل کر کام کرنے کی صلاحیت پر ایک مضبوط حد" دکھائی گئی۔ یہ پی سی پی تھیوریم کے کوانٹم اینالاگ کو ثابت کرنے کی طرف ایک قدم ہو سکتا ہے، کیونکہ جب نتیجہ میڈیا میں رپورٹ کیا گیا تو پروفیسر ڈورٹ احرونوف نے اسے "ملٹی پروور انٹرایکٹو ثبوتوں پر پہلے کے مقالے کا کوانٹم اینالاگ" قرار دیا جو "بنیادی طور پر پی سی پی تھیوریم کی طرف لے گیا"۔ 2018 میں، تھامس ویڈک اور آنند نٹراجن نے بے ترتیب تخفیف کے تحت کوانٹم پی سی پی تھیوریم کا ایک گیم ورژن ثابت کیا۔ اس میں کہا گیا ہے کہ کیو ایم اے ایم آئی پی * [لاگ (این)، 1، 1/2]، جہاں ایم آئی پی * [ایف (این)، سی، ایس] ملٹی پروور کوانٹم انٹرایکٹو پروف سسٹمز کی ایک پیچیدگی کلاس ہے جس میں ایف (این) بٹ کلاسیکی مواصلات ہیں، اور تکمیل سی ہے اور ساؤنڈنیس ایس ہے۔ انہوں نے یہ بھی ظاہر کیا کہ کوانٹم پی سی پی قیاس کا ہیملٹنین ورژن، یعنی مستقل وعدے کے فرق سی-ایس کے ساتھ ایک مقامی ہیملٹنین مسئلہ کیو ایم اے-ہارڈ ہے، گیم کوانٹم پی سی پی تھیوریم کا اشارہ کرتا ہے۔ این ایل ٹی ایس قیاس ایک بنیادی غیر حل شدہ رکاوٹ ہے اور پی سی پی کے کوانٹم اینالاگ کا پیش خیمہ ہے۔ حوالہ جات نوٹ کریں۔ ۔ ۔ ۔ ۔ ۔ کمپیوٹیشنل پیچیدگی تھیوری میں بے ترتیب الگورتھم تھیوریمز