PCP theorem
कम्प्यूटेशनल जटिलता सिद्धांत में, पी. सी. पी. प्रमेय (जिसे पी. सी. पी. लक्षण वर्णन प्रमेय के रूप में भी जाना जाता है) बताता है कि एन. पी. जटिलता वर्ग में प्रत्येक निर्णय समस्या में निरंतर प्रश्न जटिलता और लघुगणक यादृच्छिकता जटिलता (यादृच्छिक बिट्स की लघुगणक संख्या का उपयोग करता है) के संभावित रूप से जांच योग्य प्रमाण (प्रमाण जिन्हें एक यादृच्छिक एल्गोरिथ्म द्वारा जांचा जा सकता है) होते हैं। पी. सी. पी. प्रमेय कहता है कि कुछ सार्वभौमिक स्थिरांक के के लिए, प्रत्येक एन के लिए, लंबाई एन के कथन के लिए किसी भी गणितीय प्रमाण को लंबाई पॉली (एन) के एक अलग प्रमाण के रूप में फिर से लिखा जा सकता है जो एक यादृच्छिक एल्गोरिथ्म द्वारा 99 प्रतिशत सटीकता के साथ औपचारिक रूप से सत्यापित किया जा सकता है जो उस प्रमाण के केवल के अक्षरों का निरीक्षण करता है। पी. सी. पी. प्रमेय सन्निकटन की कम्प्यूटेशनल कठोरता के सिद्धांत की आधारशिला है, जो विभिन्न अनुकूलन समस्याओं के लिए कुशल सन्निकटन एल्गोरिदम तैयार करने में अंतर्निहित कठिनाई की जांच करता है। इसे इंगो वेजनर द्वारा "कुक के प्रमेय के बाद से जटिलता सिद्धांत में सबसे महत्वपूर्ण परिणाम" के रूप में वर्णित किया गया है और ओडेड गोल्डरिच द्वारा "नवीन विचारों से समृद्ध प्रभावशाली कार्यों के अनुक्रम की पराकाष्ठा" के रूप में वर्णित किया गया है। औपचारिक कथन पीसीपी प्रमेय बताता है कि एनपी = पीसीपी [ओ (लॉग एन), ओ (1)], जहाँ पीसीपी [आर (एन), क्यू (एन)] समस्याओं का वह वर्ग है जिसके लिए किसी समाधान का संभावित रूप से जांच योग्य प्रमाण दिया जा सकता है, जैसे कि प्रमाण को यादृच्छिकता के आर (एन) बिट्स का उपयोग करके बहुपद समय में जांचा जा सकता है और प्रमाण के क्यू (एन) बिट्स को पढ़कर, सही प्रमाण हमेशा स्वीकार किए जाते हैं, और गलत प्रमाणों को कम से कम 1/2 संभावना के साथ अस्वीकार कर दिया जाता है। एन एक समस्या उदाहरण के विवरण की लंबाई है। आगे ध्यान दें कि सत्यापन एल्गोरिथ्म गैर-अनुकूली हैः जांच करने के लिए प्रमाण के टुकड़ों का चयन केवल यादृच्छिक टुकड़ों और समस्या के उदाहरण के विवरण पर निर्भर करता है, न कि प्रमाण के वास्तविक टुकड़ों पर। पी. सी. पी. और सन्निकटन की कठोरता पी. सी. पी. प्रमेय के एक वैकल्पिक सूत्रीकरण में कहा गया है कि एक बाधा संतुष्टि समस्या की संतोषजनक बाधाओं का अधिकतम अंश कुछ स्थिर कारक के भीतर एन. पी.-कठिन से अनुमानित है। औपचारिक रूप से, कुछ स्थिरांकों q और α <1 के लिए, निम्नलिखित वचन समस्या (लाइज़, Lno) एक एन. पी.-कठिन निर्णय समस्या हैः लाइज़ = {φ: में सभी बाधाएं एक साथ संतोषजनक हैं} Lno = {φ: प्रत्येक कार्य φ की बाधाओं के एक α अंश से कम को संतुष्ट करता है}, जहां φ प्रति बाधा अधिकतम q चर के साथ एक बूलियन वर्णमाला पर एक बाधा संतुष्टि समस्या (सी. एस. पी.) है। ऊपर उल्लिखित वर्ग पी. सी. पी. के साथ संबंध को यह देखते हुए देखा जा सकता है कि एक प्रमाण में बिट्स क्यू की एक स्थिर संख्या की जाँच को प्रमाण के उन बिट्स पर क्यू बूलियन चर में एक बाधा का मूल्यांकन करने के रूप में देखा जा सकता है। चूँकि सत्यापन एल्गोरिथ्म यादृच्छिकता के ओ (लॉग एन) बिट्स का उपयोग करता है, इसलिए इसे सी. एस. पी. के रूप में दर्शाया जा सकता है जैसा कि पॉली (एन) बाधाओं के साथ ऊपर वर्णित है। पी. सी. पी. प्रमेय का दूसरा लक्षण वर्णन तब α = 1/2 के साथ वचन शर्त की गारंटी देता हैः यदि एन. पी. समस्या का उत्तर हाँ है, तो प्रत्येक बाधा (जो यादृच्छिक बिट्स के लिए एक विशेष मूल्य से मेल खाती है) का एक संतोषजनक कार्य (एक स्वीकार्य प्रमाण) होता है; अन्यथा, किसी भी प्रमाण को कम से कम 1/2 की संभावना के साथ अस्वीकार कर दिया जाना चाहिए, जिसका अर्थ है कि किसी भी कार्य को 1/2 से कम बाधाओं को पूरा करना चाहिए (जिसका अर्थ है कि इसे 1/2 से कम संभावना के साथ स्वीकार किया जाएगा)। इसलिए, वादा समस्या के लिए एक एल्गोरिथ्म अंतर्निहित एन. पी. समस्या को हल करने में सक्षम होगा, और इसलिए वादा समस्या एन. पी. कठिन होनी चाहिए। इस प्रमेय के परिणामस्वरूप, यह दिखाया जा सकता है कि अधिकतम बूलियन सूत्र संतोषजनकता, ग्राफ में अधिकतम स्वतंत्र सेट और जाली के लिए सबसे छोटी वेक्टर समस्या सहित कई प्राकृतिक अनुकूलन समस्याओं का समाधान कुशलता से अनुमानित नहीं किया जा सकता है जब तक कि पी = एनपी न हो। यह उपरोक्त रूप की वचन समस्या के लिए ऐसी समस्याओं के समाधान को अनुमानित करने की समस्या को कम करके किया जा सकता है। इन परिणामों को कभी-कभी पी. सी. पी. प्रमेय भी कहा जाता है क्योंकि उन्हें कुछ अतिरिक्त संरचना के साथ एन. पी. के लिए संभावित रूप से जांच योग्य प्रमाण के रूप में देखा जा सकता है। सबूत एक कमजोर परिणाम का प्रमाण, एनपी पीसीपी [एन3,1] डेक्सटर कोज़ेन के एक व्याख्यान में दिया गया है। पी. सी. पी. प्रमेय संवादात्मक प्रमाणों और संभावित रूप से जांच योग्य प्रमाणों पर काम की एक लंबी पंक्ति की पराकाष्ठा है। मानक प्रमाणों और संभावित रूप से जांच योग्य प्रमाणों से संबंधित पहला प्रमेय यह कथन है कि एन. ई. एक्स. पी. पी. सी. पी. [पॉली (एन), पॉली (एन)], द्वारा सिद्ध किया गया है। प्रारंभिक अक्षरों की उत्पत्ति पी. सी. पी. सी. (एन), एस (एन) [आर (एन), क्यू (एन)] संकेतन को संभावित रूप से जांच योग्य प्रमाण पर समझाया गया है। संकेतन एक ऐसे फलन का है जो एक निश्चित जटिलता वर्ग देता है। ऊपर दिए गए स्पष्टीकरण को देखें। इस प्रमेय का नाम ("पी. सी. पी. प्रमेय") शायद या तो "पी. सी. पी". से आता है जिसका अर्थ है "संभावित रूप से जांच योग्य प्रमाण", या ऊपर उल्लिखित संकेतन (या दोनों) से आता है। इसके बाद, इस काम में उपयोग की जाने वाली विधियों को 1991 में बाबई, लांस फोर्टनो, लेविन और सेजेडी, फीज, गोल्डवासर, लुंड, सफरा और सेजेडी (1991), और 1992 में अरोड़ा और सफरा द्वारा अरोरा, लुंड, मोटवानी, सूडान और सेजेडी द्वारा 1998 में पी. सी. पी. प्रमेय का प्रमाण देने के लिए विस्तारित किया गया था। 2001 का गोडेल पुरस्कार संजीव अरोड़ा, यूरियल फीगे, शफी गोल्डवासर, कार्स्टन लुंड, लेज़लो लोवाज़, राजीव मोटवानी, श्मुएल सफरा, मधु सुदान और मारियो सेजेडी को पी. सी. पी. प्रमेय पर काम करने और अनुमान की कठोरता से इसके संबंध के लिए प्रदान किया गया था। 2005 में इरिट दिनूर ने विस्तारक ग्राफ का उपयोग करके पी. सी. पी. प्रमेय का एक काफी सरल प्रमाण खोजा। इसके लिए उन्हें 2019 का गोडेल पुरस्कार मिला। क्वांटम एनालॉग 2012 में, थॉमस विडिक और त्सुयोशी इतो ने एक परिणाम प्रकाशित किया जिसने "एक मल्टीप्लेयर गेम में उलझने वाले प्रोवर्स की क्षमता पर एक मजबूत सीमा" दिखाई। यह पी. सी. पी. प्रमेय के क्वांटम एनालॉग को साबित करने की दिशा में एक कदम हो सकता है, क्योंकि जब परिणाम मीडिया में रिपोर्ट किया गया था, तो प्रोफेसर डोरिट अहरोनोव ने इसे "मल्टीप्रोवर इंटरैक्टिव प्रूफ पर पहले के पेपर का क्वांटम एनालॉग" कहा जो "मूल रूप से पी. सी. पी. प्रमेय की ओर ले गया"। 2018 में, थॉमस विडिक और आनंद नटराजन ने यादृच्छिक कमी के तहत क्वांटम पी. सी. पी. प्रमेय का एक गेम संस्करण साबित किया। यह बताता है कि क्यूएमए एमआईपी * [लॉग (एन), 1,1/2], जहां एमआईपी * [एफ (एन), सी, एस] एफ (एन)-बिट शास्त्रीय संचार के साथ बहु-प्रमाण क्वांटम इंटरैक्टिव प्रूफ सिस्टम का एक जटिलता वर्ग है, और पूर्णता सी है और ध्वनि एस है। उन्होंने यह भी दिखाया कि क्वांटम पीसीपी अनुमान का हैमिल्टनियन संस्करण, अर्थात् निरंतर वादा अंतराल सी-एस के साथ एक स्थानीय हैमिल्टनियन समस्या क्यूएमए-हार्ड है, जो खेल क्वांटम पीसीपी प्रमेय को दर्शाता है। एन. एल. टी. एस. अनुमान पी. सी. पी. के क्वांटम एनालॉग के लिए एक मौलिक अनसुलझी बाधा और अग्रदूत है। टिप्पणियाँ संदर्भ। .. .. .. .. .. कम्प्यूटेशनल जटिलता सिद्धांत में यादृच्छिक एल्गोरिदम प्रमेय