सह-एनपी-पूर्ण
जटिलता सिद्धांत में, कम्प्यूटेशनल समस्याएं जो co-NP-complete हैं, वे हैं जो co-NP में सबसे अधिक समस्याएं हैं, इस अर्थ में कि co-NP में किसी भी समस्या को केवल बहुपद ओवरहेड के साथ किसी भी को-एनपी-पूर्ण समस्या के एक विशेष स्थिति के रूप में सुधार किया जा सकता है। यदि P co-NP से अलग है, तो सभी co-NP-complete समस्याएं बहुपद समय में हल करने योग्य नहीं हैं। यदि co-NP-complete समस्या को शीघ्र हल करने की कोई विधि उपस्थित है, तो उस एल्गोरिथ्म का उपयोग सभी co-NP समस्याओं को शीघ्रता से हल करने के लिए किया जा सकता है।
प्रत्येक सह-एनपी-पूर्ण समस्या एनपी-पूर्ण समस्या की पूरक (जटिलता) है। एनपी (जटिलता) और सह-एनपी दोनों में कुछ समस्याएं हैं, उदाहरण के लिए पी (जटिलता) या पूर्णांक गुणनखंडन में सभी समस्याएं। हालाँकि, यह ज्ञात नहीं है कि क्या सेट समान हैं, हालाँकि असमानता की संभावना अधिक मानी जाती है। अधिक विवरण के लिए सह-एनपी और एनपी-पूर्ण देखें।
फॉर्च्यून ने 1979 में दिखाया कि यदि कोई भी विरल भाषा सह-एनपी-पूर्ण (या यहां तक कि केवल सह-एनपी-हार्ड) है, तो P = NP,[1] महाने के प्रमेय के लिए एक महत्वपूर्ण आधार।
औपचारिक परिभाषा
एक निर्णय समस्या C सह-एनपी-पूर्ण है यदि यह सह-एनपी में है और यदि सह-एनपी में प्रत्येक समस्या बहुपद-समय अनेक-एक कमी है|बहुपद-समय अनेक-एक इसके लिए न्यूनीकरणीय है।[2] इसका मतलब यह है कि प्रत्येक सह-एनपी समस्या एल के लिए, एक बहुपद समय एल्गोरिदम मौजूद है जो एल के किसी भी उदाहरण को समान सत्य मान के साथ सी के उदाहरण में बदल सकता है। परिणामस्वरूप, यदि हमारे पास 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.
