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