सह-एनपी-पूर्ण
जटिलता सिद्धांत में, कम्प्यूटेशनल समस्याएं जो सह-एनपी-पूर्ण हैं, वे हैं जो सह-एनपी में सबसे अधिक समस्याएं हैं, इस अर्थ में कि सह-एनपी में किसी भी समस्या को केवल बहुपद ओवरहेड के साथ किसी भी सह-एनपी-पूर्ण समस्या के एक विशेष स्थिति के रूप में सुधार किया जा सकता है। यदि P सह-एनपी से अलग है, तो सभी सह-एनपी-पूर्ण समस्याएं बहुपद समय में हल करने योग्य नहीं हैं। यदि सह-एनपी-पूर्ण समस्या को शीघ्र हल करने की कोई विधि उपस्थित है, तो उस एल्गोरिथ्म का उपयोग सभी सह-एनपी समस्याओं को शीघ्रता से हल करने के लिए किया जा सकता है।
प्रत्येक सह-एनपी-पूर्ण समस्या दूसरी एनपी-पूर्ण समस्या की पूरक है। एनपी और सह-एनपी दोनों में कुछ समस्याएं हैं, उदाहरण के लिए P या पूर्णांक गुणनखंडन में सभी समस्याएं हैं। हालाँकि, यह ज्ञात नहीं है कि क्या समूह समान हैं, हालाँकि असंतुलन की संभावना अधिक मानी जाती है। अधिक जानकारी के लिए सह-एनपी और एनपी-पूर्ण देखें।
फॉर्च्यून ने 1979 में दिखाया कि यदि कोई स्पार्स लैंग्वेज सह-एनपी-पूर्ण (या यहां तक कि सिर्फ सह-एनपी-हार्ड), तो P = NP[1] महाने की प्रमेय के लिए महत्वपूर्ण आधार है।
औपचारिक परिभाषा
निर्णय समस्या C सह-एनपी-पूर्ण है यदि यह सह-एनपी में है और यदि सह-एनपी में हर समस्या बहुपद-समय है तो कई-एक इसके लिए पुनर्वितरण योग्य है।[2] इसका तात्पर्य यह है कि प्रत्येक सह-एनपी समस्या L के लिए, बहुपद समय एल्गोरिथ्म उपस्थित है जो L के किसी भी उदाहरण को C के उदाहरण में समान सत्य मान के साथ बदल सकता है। परिणामस्वरूप, यदि हमारे पास C के लिए एक बहुपद समय एल्गोरिथ्म था, तो हम बहुपद समय में सभी सह-एनपी समस्याओं को हल कर सकते हैं।
उदाहरण
सह-एनपी-पूर्ण समस्या का एक उदाहरण टॉटोलॉजी है, यह निर्धारित करने की समस्या कि क्या कोई दिया गया बूलियन सूत्र टॉटोलॉजी है; अर्थात्, क्या चरों के लिए सही/गलत मानों का प्रत्येक संभावित असाइनमेंट एक सही कथन उत्पन्न करता है। यह बूलियन संतुष्टि समस्या से निकटता से संबंधित है, जो बताता है कि क्या कम से कम एक ऐसा असाइनमेंट उपस्थित है, और एनपी-पूर्ण है।[2]
संदर्भ
- ↑ Fortune, S. (1979). "विरल पूर्ण सेट पर एक नोट" (PDF). SIAM Journal on Computing. 8 (3): 431–433. doi:10.1137/0208034. hdl:1813/7473.
- ↑ 2.0 2.1 Arora, Sanjeev; Barak, Boaz (2009). Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4.
