सह-एनपी

Unsolved problem in computer science:

${\textsf {NP}}\ {\overset {?}{=}}\ {\textsf {co-NP}}$

(more unsolved problems in computer science)

कम्प्यूटेशनल जटिलता सिद्धांत में, सह-एनपी एक जटिलता वर्ग है। एक निर्णय समस्या एक्स सह-एनपी का सदस्य है अगर और केवल अगर इसकी पूरक (जटिलता) X जटिलता वर्ग एनपी (जटिलता) में है। वर्ग को निम्नानुसार परिभाषित किया जा सकता है: एक निर्णय समस्या सह-एनपी में ठीक है यदि केवल नो-इंस्टेंस में बहुपद-लंबाई प्रमाणपत्र (जटिलता) है और एक बहुपद-समय एल्गोरिथ्म है जिसका उपयोग किसी भी कथित प्रमाण पत्र को सत्यापित करने के लिए किया जा सकता है।

अर्थात्, 'co-NP' निर्णय समस्याओं का समुच्चय है जहाँ एक बहुपद मौजूद है $p(n)$ और एक बहुपद-समयबद्ध ट्यूरिंग मशीन एम जैसे कि प्रत्येक उदाहरण के लिए एक्स, एक्स एक नो-इंस्टेंस है अगर और केवल अगर: लंबाई के कुछ संभावित प्रमाण पत्र सी के लिए $p(n)$, ट्यूरिंग मशीन M जोड़ी को स्वीकार करती है (x, c).

पूरक समस्याएं

Main article: Complement (complexity)

जबकि एक एनपी समस्या पूछती है कि क्या दिया गया उदाहरण हां-उदाहरण है, इसका पूरक पूछता है कि क्या कोई उदाहरण नहीं है, जिसका अर्थ है कि पूरक सह-एनपी में है। मूल एनपी समस्या के लिए कोई भी हां-उदाहरण इसके पूरक के लिए नहीं-उदाहरण बन जाता है, और इसके विपरीत।

असंतोष

Further information: Unsatisfiable core

एनपी-पूर्ण समस्या का एक उदाहरण बूलियन संतुष्टि समस्या है: एक बूलियन सूत्र दिया गया है, क्या यह संतोषजनक है (क्या कोई संभावित इनपुट है जिसके लिए सूत्र सही है)? पूरक समस्या पूछती है: एक बूलियन फॉर्मूला दिया गया है, क्या यह असंतोषजनक है (फॉर्मूला आउटपुट के सभी संभावित इनपुट गलत हैं)? . चूंकि यह संतुष्टि की समस्या का पूरक है, इसलिए बिना किसी उदाहरण के प्रमाण पत्र मूल एनपी समस्या से हां-उदाहरण के समान है: बूलियन वैरिएबल असाइनमेंट का एक सेट जो सूत्र को सत्य बनाता है। दूसरी ओर, पूरक समस्या के लिए हां-उदाहरण का प्रमाण पत्र उतना ही जटिल होगा जितना कि मूल एनपी संतुष्टि समस्या का उदाहरण नहीं।

दोहरी समस्याएं

Main article: Duality (optimization)

सह-एनपी-पूर्णता

Main article: co-NP-complete

एक समस्या एल सह-एनपी-पूर्ण है अगर और केवल अगर एल सह-एनपी में है और सह-एनपी में किसी भी समस्या के लिए, उस समस्या से एल तक बहुपद-समय की कमी मौजूद है।

टॉटोलॉजी रिडक्शन

यह निर्धारित करना कि क्या प्रस्तावपरक तर्क में एक सूत्र एक तनातनी (तर्क) है, सह-एनपी-पूर्ण है: अर्थात, यदि सूत्र अपने चर के लिए हर संभव असाइनमेंट के तहत सही का मूल्यांकन करता है।

अन्य वर्गों से संबंध

Further information: Complexity class

पी (जटिलता), एनपी (जटिलता), सह-एनपी, बीपीपी (जटिलता), पी/पॉली, पीएच (जटिलता), और पीएसपीएसीई सहित जटिलता वर्गों का समावेश

पी (जटिलता), बहुपद समय हल करने योग्य समस्याओं का वर्ग, एनपी और सह-एनपी दोनों का एक सबसेट है। P को दोनों मामलों में एक सख्त उपसमुच्चय माना जाता है (और स्पष्ट रूप से एक मामले में सख्त नहीं हो सकता है और दूसरे में सख्त नहीं है)।

एनपी और सह-एनपी को भी असमान माना जाता है। यदि ऐसा है, तो कोई एनपी-पूर्ण समस्या सह-एनपी में नहीं हो सकती है और कोई सह-एनपी-पूर्ण समस्या एनपी में नहीं हो सकती है। इसे इस प्रकार दिखाया जा सकता है। मान लीजिए विरोधाभास के लिए एक एनपी-पूर्ण समस्या मौजूद है X जो सह-एनपी में है। चूंकि एनपी में सभी समस्याओं को कम किया जा सकता है X, यह इस प्रकार है कि एनपी में हर समस्या के लिए, हम एक गैर-नियतात्मक ट्यूरिंग मशीन का निर्माण कर सकते हैं जो बहुपद समय में इसके पूरक का निर्णय लेती है; अर्थात।, ${\textsf {NP}}\subseteq {\textsf {co-NP}}$. इससे, यह इस प्रकार है कि एनपी में समस्याओं के पूरक का सेट सह-एनपी में समस्याओं के पूरक के सेट का एक सबसेट है; अर्थात।, ${\textsf {co-NP}}\subseteq {\textsf {NP}}$. इस प्रकार ${\textsf {co-NP}}={\textsf {NP}}$. सबूत है कि एनपी में कोई सह-एनपी-पूर्ण समस्या नहीं हो सकती है ${\textsf {NP}}\neq {\textsf {co-NP}}$ सममित है।

सह-एनपी PH (जटिलता) का एक सबसेट है, जो स्वयं PSPACE का एक सबसेट है।

पूर्णांक गुणनखंड

Main article: Integer factorization

एक समस्या का एक उदाहरण जो एनपी और सह-एनपी दोनों से संबंधित है (लेकिन पी में नहीं जाना जाता है) Integer_factorization#Difficulty_and_complexity है: सकारात्मक पूर्णांक m और n दिया गया है, यह निर्धारित करें कि क्या m का कारक n से कम है और इससे अधिक है एक। एनपी में सदस्यता स्पष्ट है; यदि m में ऐसा गुणनखंड है, तो गुणनखंड स्वयं एक प्रमाण पत्र है। सह-एनपी में सदस्यता भी सीधी है: कोई केवल एम के प्रमुख कारकों को सूचीबद्ध कर सकता है, सभी अधिक या एन के बराबर, जो सत्यापनकर्ता गुणन और एकेएस प्रारंभिक परीक्षण द्वारा मान्य होने की पुष्टि कर सकता है। वर्तमान में यह ज्ञात नहीं है कि गुणनखंडन के लिए एक बहुपद-समय एल्गोरिथ्म है या नहीं, समतुल्य रूप से पूर्णांक गुणनखंड P में है, और इसलिए यह उदाहरण एनपी और सह-एनपी में ज्ञात सबसे प्राकृतिक समस्याओं में से एक के रूप में दिलचस्प है, लेकिन इसके लिए ज्ञात नहीं है। पी में हो

बाहरी संबंध

• Complexity Zoo: coNP