Unique games conjecture
कम्प्यूटेशनल जटिलता सिद्धांत में, अद्वितीय खेल अनुमान (जिसे अक्सर यू. जी. सी. के रूप में संदर्भित किया जाता है) 2002 में सुभाष खोट द्वारा बनाया गया एक अनुमान है। अनुमान यह मानता है कि एक निश्चित प्रकार के खेल के अनुमानित मूल्य को निर्धारित करने की समस्या, जिसे एक अद्वितीय खेल के रूप में जाना जाता है, में एनपी-हार्ड कम्प्यूटेशनल जटिलता होती है। सन्निकटन की कठोरता के सिद्धांत में इसके व्यापक अनुप्रयोग हैं। यदि अद्वितीय खेल अनुमान सही है और पी  ऒत्त एन. पी. है, तो कई महत्वपूर्ण समस्याओं के लिए बहुपद समय में एक सटीक समाधान प्राप्त करना न केवल असंभव है (जैसा कि पी बनाम एन. पी. समस्या द्वारा प्रतिपादित किया गया है), बल्कि एक अच्छा बहुपद-समय सन्निकटन प्राप्त करना भी असंभव है। जिन समस्याओं के लिए इस तरह की असंगतता का परिणाम होगा, उनमें बाधा संतुष्टि की समस्याएं शामिल हैं, जो विभिन्न प्रकार के विषयों में सामने आती हैं। यह अनुमान इस मायने में असामान्य है कि अकादमिक दुनिया इस बात पर समान रूप से विभाजित प्रतीत होती है कि यह सच है या नहीं। अद्वितीय खेल अनुमान को कई समान तरीकों से कहा जा सकता है। अद्वितीय लेबल आवरण अद्वितीय खेल अनुमान के निम्नलिखित सूत्रीकरण का उपयोग अक्सर सन्निकटन की कठोरता में किया जाता है। अनुमान निम्नलिखित वादा समस्या की एन. पी.-कठोरता को प्रस्तुत करता है जिसे अद्वितीय बाधाओं के साथ लेबल कवर के रूप में जाना जाता है। प्रत्येक किनारे के लिए, दो शीर्षों पर रंग कुछ विशेष क्रमबद्ध जोड़े तक सीमित हैं। अद्वितीय बाधाओं का मतलब है कि प्रत्येक किनारे के लिए किसी भी क्रमबद्ध जोड़े में एक ही नोड के लिए समान रंग नहीं होता है। इसका मतलब है कि आकार 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 में पेश किया गया था ताकि अनुमान की कठोरता के सिद्धांत में कुछ प्रश्नों पर प्रगति की जा सके। अद्वितीय खेल अनुमान की सच्चाई कई ज्ञात सन्निकटन एल्गोरिदम की इष्टतमता का संकेत देगी (पी ≤ एन. पी. मानते हुए)। उदाहरण के लिए, एक ग्राफ में अधिकतम कटौती का अनुमान लगाने के लिए गोमैन और विलियमसन के एल्गोरिथ्म द्वारा प्राप्त सन्निकटन अनुपात किसी भी योगात्मक स्थिरांक के भीतर अद्वितीय खेल अनुमान और पी ≤ एन. पी. को मानते हुए इष्टतम है। परिणामों की एक सूची जिसे अद्वितीय खेल अनुमान का संकेत देने के लिए जाना जाता है, निकटवर्ती तालिका में कमजोर धारणा पी ≤ एन. पी. के लिए संबंधित सर्वोत्तम परिणामों के साथ दिखाया गया है। एक स्थिरांक या इसका मतलब है कि परिणाम प्रत्येक स्थिरांक (समस्या के आकार के संबंध में) के लिए क्रमशः उससे अधिक या उससे कम होता है। चर्चा और विकल्प वर्तमान में, अद्वितीय खेल अनुमान की सच्चाई के बारे में कोई आम सहमति नहीं है। अनुमान के कुछ मजबूत रूपों को अस्वीकार कर दिया गया है। अनुमान का एक अलग रूप यह मानता है कि जब एक अद्वितीय खेल का मूल्य कम से कम उस मामले से अलग होता है जब मूल्य अधिक से अधिक होता है तो बहुपद-समय एल्गोरिदम (लेकिन शायद एनपी-हार्ड नहीं) के लिए असंभव है। अनुमान का यह रूप अभी भी सन्निकटन की कठोरता में अनुप्रयोगों के लिए उपयोगी होगा। अनुमान के उपरोक्त सूत्रीकरणों में स्थिरांक तब तक आवश्यक है जब तक कि पी = एनपी न हो। यदि विशिष्टता की आवश्यकता को हटा दिया जाता है तो संबंधित कथन को समानांतर पुनरावृत्ति प्रमेय द्वारा सही माना जाता है, यहां तक कि मारेक कार्पिंस्की और वारेन शूडी ने अद्वितीय खेल समस्या के घने उदाहरणों के लिए रैखिक समय सन्निकटन योजनाओं का निर्माण किया है। 2008 में, प्रसाद राघवेंद्र ने दिखाया है कि यदि अद्वितीय खेल अनुमान सही है, तो प्रत्येक बाधा संतुष्टि समस्या के लिए सबसे अच्छा सन्निकटन अनुपात एक निश्चित सरल अर्ध-परिमित प्रोग्रामिंग उदाहरण द्वारा दिया जाता है, जो विशेष रूप से बहुपद है। 2010 में, प्रसाद राघवेंद्र और डेविड स्टीयरर ने गैप-स्मॉल-सेट विस्तार समस्या को परिभाषित किया, और अनुमान लगाया कि यह एनपी-हार्ड है। यह अनुमान अद्वितीय खेल अनुमान का संकेत देता है। इसका उपयोग पूर्ण द्विदलीय उपलेख खोजने के लिए सन्निकटन परिणामों की मजबूत कठोरता साबित करने के लिए भी किया गया है। 2010 में, संजीव अरोड़ा, बोआज़ बराक और डेविड स्टीयरर ने अद्वितीय खेल समस्या के लिए एक उप-घातीय समय सन्निकटन एल्गोरिथ्म की खोज की। 2012 में, यह दिखाया गया था कि कम से कम मूल्य वाले उदाहरणों से अधिक से अधिक मूल्य वाले उदाहरणों को अलग करना एनपी-हार्ड है। 2018 में, कागजों की एक श्रृंखला के बाद, अनुमान का एक कमजोर संस्करण, जिसे 2-2 खेल अनुमान कहा जाता है, साबित हुआ। एक निश्चित अर्थ में, यह मूल अनुमान का "आधा" साबित करता है। यह अद्वितीय लेबल आवरण के लिए सबसे प्रसिद्ध अंतर में भी सुधार करता हैः कम से कम मूल्य वाले उदाहरणों से अधिक से अधिक मूल्य वाले उदाहरणों को अलग करना एन. पी.-कठिन है। टिप्पणियाँ संदर्भ। 2002 सन्निकटन एल्गोरिदम की गणना में कम्प्यूटेशनल जटिलता सिद्धांत कम्प्यूटेशनल कठोरता धारणाएँ कंप्यूटर विज्ञान में अनसुलझी समस्याएं अनुमान