सह-एनपी: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{unsolved|कंप्यूटर विज्ञान|{{tmath|1=\textsf{NP}\ \overset{?}{=}\ \textsf{co-NP} }} }}
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, '''सह-एनपी''' एक [[जटिलता वर्ग]] है। एक [[निर्णय समस्या]] एक्स सह-एनपी का सदस्य है यदि और केवल यदि इसकी [[पूरक (जटिलता)]] एक्स जटिलता वर्ग [[एनपी (जटिलता)]] में है। वर्ग को निम्नानुसार परिभाषित किया जा सकता है: एक निर्णय समस्या सह-एनपी में ठीक है यदि और केवल नो-इंस्टेंस में बहुपद-लंबाई [[प्रमाणपत्र (जटिलता)]] है और बहुपद-समय एल्गोरिथ्म है जिसका उपयोग किसी भी कथित प्रमाण पत्र को सत्यापित करने के लिए किया जा सकता है।
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, '''सह-एनपी''' [[जटिलता वर्ग]] होता है। चूँकि [[निर्णय समस्या]] एक्स सह-एनपी का सदस्य होता है और यदि इसकी [[पूरक (जटिलता)]] {{overline|X}} जटिलता वर्ग [[एनपी (जटिलता)]] में होती है। इस प्रकार वर्ग को निम्नानुसार परिभाषित किया जा सकता है, अतः निर्णय समस्या सह-एनपी में ठीक होता है यदि केवल कोई प्रत्येक गैर-उदाहरण के लिए हमारे समीप बहुपद-लंबाई [[प्रमाणपत्र (जटिलता)|"प्रमाणपत्र" (जटिलता)]] होती है और बहुपद-समय एल्गोरिथ्म होता है, जिसका उपयोग किसी भी कथित प्रमाण पत्र को सत्यापित करने के लिए किया जा सकता है।


अर्थात्, 'सह-एनपी' निर्णय समस्याओं का समुच्चय होता है, जहाँ बहुपद {{tmath|p(n)}} उपस्तिथ होता है और बहुपद-समयबद्ध [[ट्यूरिंग मशीन]] एम जैसे कि प्रत्येक उदाहरण के लिए एक्स, एक्स में कोई उदाहरण नहीं होता है और यदि लंबाई के कुछ संभावित प्रमाण पत्र c के लिए {{tmath|p(n)}}, ट्यूरिंग मशीन M जोड़ी {{math|(''x'', ''c'')}} को स्वीकार करती है।<ref name="A&B">{{cite book |last1= Arora |first1= Sanjeev |last2= Barak |first2= Boaz |url= http://www.cs.princeton.edu/theory/complexity/ |title= Complexity Theory: A Modern Approach |publisher= Cambridge University Press |date= 2009 |isbn= 978-0-521-42426-4 |page=56 }}</ref>
अर्थात्, 'सह-एनपी' निर्णय समस्याओं का समुच्चय है जहाँ बहुपद उपस्तिथ है पी(एन) और बहुपद-समयबद्ध [[ट्यूरिंग मशीन]] एम जैसे कि प्रत्येक उदाहरण के लिए एक्स, एक्स नो-इंस्टेंस है यदि और केवल यदि: लंबाई के कुछ संभावित प्रमाण पत्र सी के लिए पी(एन), ट्यूरिंग मशीन एम जोड़ी (एक्स, सी) को स्वीकार करती है। <ref name="A&B">{{cite book |last1= Arora |first1= Sanjeev |last2= Barak |first2= Boaz |url= http://www.cs.princeton.edu/theory/complexity/ |title= Complexity Theory: A Modern Approach |publisher= Cambridge University Press |date= 2009 |isbn= 978-0-521-42426-4 |page=56 }}</ref>
== पूरक समस्याएं ==
== पूरक समस्याएं ==
{{main|पूरक (जटिलता)}}
जबकि एक एनपी समस्या पूछती है कि क्या दिया गया उदाहरण हां-उदाहरण है, इसका पूरक पूछता है कि क्या कोई उदाहरण नहीं है, जिसका अर्थ है कि पूरक सह-एनपी में है और इसके विपरीत मूल एनपी समस्या के लिए कोई भी हां-उदाहरण इसके पूरक के लिए नहीं-उदाहरण बन जाता है।
सामान्यतः एनपी समस्या पूछती है कि क्या दिया गया उदाहरण हां-उदाहरण है, इसका पूरक पूछता है कि क्या कोई उदाहरण नहीं होता है, जिसका अर्थ यह होता है कि पूरक सह-एनपी में है। इस प्रकार मूल एनपी समस्या के लिए कोई भी हां-उदाहरण इसके पूरक के लिए नहीं-उदाहरण बन जाता है और इसके विपरीत होता है।


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


== दोहरी समस्याएं ==
== दोहरी समस्याएं ==
{{main|द्वैत (अनुकूलन)}}
== सह-एनपी-पूर्णता ==
== सह-एनपी-पूर्णता ==
{{main|सह-एनपी-पूर्ण}}
एक समस्या एल [[सह-एनपी-पूर्ण]] है यदि और केवल यदि एल सह-एनपी में है और सह-एनपी में किसी भी समस्या के लिए, उस समस्या से एल तक बहुपद-समय की कमी उपस्तिथ है।
समस्या एल [[सह-एनपी-पूर्ण]] होती है और यदि एल सह-एनपी में है और सह-एनपी में किसी भी समस्या के लिए, उस समस्या से एल तक बहुपद-समय की कमी उपस्तिथ होती है।


=== टॉटोलॉजी कमी ===
=== टॉटोलॉजी रिडक्शन ===
यह निर्धारित किया जाता है कि क्या प्रस्तावपरक तर्क में सूत्र तनातनी (तर्क) होता है, अतः सह-एनपी-पूर्ण होता है। अर्थात्, यदि सूत्र अपने चर के लिए प्रत्येक संभव कार्य के अनुसार सही का मूल्यांकन करता है।<ref name="A&B"/>
यह निर्धारित करना कि क्या प्रस्तावपरक तर्क में सूत्र एक पुनरुक्ति है, सह-एनपी-पूर्ण है: अर्थात, यदि सूत्र अपने चरों के लिए हर संभव असाइनमेंट के अनुसार सही का मूल्यांकन करता है।<ref name="A&B"/>
== अन्य वर्गों से संबंध ==
== अन्य वर्गों से संबंध ==
{{further|जटिलता वर्ग}}
[[Image:Complexity-classes-polynomial.svg|thumb|[[पी (जटिलता)]], एनपी (जटिलता), सह-एनपी, [[बीपीपी (जटिलता)]], पी/पॉली, [[पीएच (जटिलता)]], और [[पीएसपीएसीई]] सहित जटिलता वर्गों का समावेश]]पी (जटिलता), बहुपद समय हल करने योग्य समस्याओं का वर्ग, एनपी और सह-एनपी दोनों का सबसेट है। पी को दोनों स्थितियों में सख्त उपसमुच्चय माना जाता है (और स्पष्ट रूप से स्थिति में सख्त नहीं हो सकता है और दूसरे में सख्त नहीं है)।


[[Image:Complexity-classes-polynomial.svg|thumb|[[पी (जटिलता)]], एनपी (जटिलता), सह-एनपी, [[बीपीपी (जटिलता)]], पी/पॉली, [[पीएच (जटिलता)]], और [[पीएसपीएसीई]] सहित जटिलता वर्गों का समावेश होता है।]]पी (जटिलता), बहुपद समय हल करने योग्य समस्याओं का वर्ग, एनपी और सह-एनपी दोनों का उपसमूह होता है। इस प्रकार पी को दोनों स्थितियों में सख्त उपसमुच्चय माना जाता है (और स्पष्ट रूप से स्थिति में सख्त नहीं हो सकता है और दूसरे में सख्त नहीं होता है)।
एनपी और सह-एनपी को भी असमान माना जाता है।<ref>{{cite book | first = John E. | last = Hopcroft | title = ऑटोमेटा सिद्धांत, भाषाएं और संगणना का परिचय| publisher = Addison-Wesley | location = Boston | year = 2000 | isbn = 0-201-44124-1 | edition = 2nd }} Chap. 11.</ref> यदि ऐसा है, तो कोई एनपी-पूर्ण समस्या सह-एनपी में नहीं हो सकती है और कोई सह-एनपी-पूर्ण समस्या एनपी में नहीं हो सकती है।<ref>{{cite book | title = P, NP, and NP-completeness: The Basics of Computational Complexity | last1 = Goldreich | first1 = Oded | publisher = [[Cambridge University Press]] | year = 2010 | page = 155 | authorlink = Oded Goldreich | isbn = 9781139490092 }}</ref> इसे इस प्रकार दिखाया जा सकता है। मान लीजिए विरोधाभास के लिए एनपी-पूर्ण समस्या उपस्तिथ है  जो सह-एनपी में है। चूंकि एनपी में सभी समस्याओं को एक्स तक कम किया जा सकता है, यह इस प्रकार है कि एनपी में हर समस्या के लिए, हम [[गैर-नियतात्मक ट्यूरिंग मशीन]] का निर्माण कर सकते हैं जो बहुपद समय में इसके पूरक का निर्णय लेती है; अर्थात इससे, यह इस प्रकार है कि एनपी में समस्याओं के पूरक का सेट सह-एनपी में समस्याओं के पूरक के सेट का सबसेट है; अर्थात, इस प्रकार सबूत है कि एनपी में कोई सह-एनपी-पूर्ण समस्या नहीं हो सकती है एनपी ≠ सह-एनपी सममित है।


एनपी और सह-एनपी को भी असमान माना जाता है।<ref>{{cite book | first = John E. | last = Hopcroft | title = ऑटोमेटा सिद्धांत, भाषाएं और संगणना का परिचय| publisher = Addison-Wesley | location = Boston | year = 2000 | isbn = 0-201-44124-1 | edition = 2nd }} Chap. 11.</ref> यदि ऐसा होता है, तब कोई एनपी-पूर्ण समस्या सह-एनपी में नहीं हो सकती है और कोई सह-एनपी-पूर्ण समस्या एनपी में नहीं हो सकती है।<ref>{{cite book | title = P, NP, and NP-completeness: The Basics of Computational Complexity | last1 = Goldreich | first1 = Oded | publisher = [[Cambridge University Press]] | year = 2010 | page = 155 | authorlink = Oded Goldreich | isbn = 9781139490092 }}</ref> इसे इस प्रकार दिखाया जा सकता है। मान लीजिए विरोधाभास के लिए एनपी-पूर्ण समस्या {{mathcal|X}} उपस्तिथ होती है, जो सह-एनपी में होता है। चूंकि एनपी में सभी समस्याओं {{mathcal|X}} को कम किया जा सकता है, यह इस प्रकार है कि एनपी में प्रत्येक समस्या के लिए, हम [[गैर-नियतात्मक ट्यूरिंग मशीन]] का निर्माण कर सकते हैं जो बहुपद समय में इसके पूरक का निर्णय लेती है। अर्थात्, {{tmath|\textsf{NP} \subseteq \textsf{co-NP} }} इससे, यह इस प्रकार है कि एनपी में समस्याओं के पूरक का समूह सह-एनपी में समस्याओं के पूरक के समूह का उपसमूह होता है। अर्थात्, {{tmath|\textsf{co-NP} \subseteq \textsf{NP} }} इस प्रकार {{tmath|1=\textsf{co-NP} = \textsf{NP} }} प्रमाण होता है कि एनपी में कोई सह-एनपी-पूर्ण समस्या नहीं हो सकती है, अतः इसमें {{tmath|\textsf{NP} \neq \textsf{co-NP} }} सममित होता है।
सह-एनपी पीएच (जटिलता) का एक उपसमुच्चय है, जो स्वयं पीएसपीएसीई का सबसेट है।
 
सह-एनपी पीएच (जटिलता) का उपसमूह होता है, जो स्वयं पीएसपीएसीई का उपसमूह होता है।


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


== संदर्भ ==
== संदर्भ ==

Revision as of 22:46, 19 June 2023

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

अर्थात्, 'सह-एनपी' निर्णय समस्याओं का समुच्चय है जहाँ बहुपद उपस्तिथ है पी(एन) और बहुपद-समयबद्ध ट्यूरिंग मशीन एम जैसे कि प्रत्येक उदाहरण के लिए एक्स, एक्स नो-इंस्टेंस है यदि और केवल यदि: लंबाई के कुछ संभावित प्रमाण पत्र सी के लिए पी(एन), ट्यूरिंग मशीन एम जोड़ी (एक्स, सी) को स्वीकार करती है। [1]

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

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

असंतोष

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

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

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

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

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

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

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

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

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

एनपी और सह-एनपी को भी असमान माना जाता है।[2] यदि ऐसा है, तो कोई एनपी-पूर्ण समस्या सह-एनपी में नहीं हो सकती है और कोई सह-एनपी-पूर्ण समस्या एनपी में नहीं हो सकती है।[3] इसे इस प्रकार दिखाया जा सकता है। मान लीजिए विरोधाभास के लिए एनपी-पूर्ण समस्या उपस्तिथ है जो सह-एनपी में है। चूंकि एनपी में सभी समस्याओं को एक्स तक कम किया जा सकता है, यह इस प्रकार है कि एनपी में हर समस्या के लिए, हम गैर-नियतात्मक ट्यूरिंग मशीन का निर्माण कर सकते हैं जो बहुपद समय में इसके पूरक का निर्णय लेती है; अर्थात इससे, यह इस प्रकार है कि एनपी में समस्याओं के पूरक का सेट सह-एनपी में समस्याओं के पूरक के सेट का सबसेट है; अर्थात, इस प्रकार सबूत है कि एनपी में कोई सह-एनपी-पूर्ण समस्या नहीं हो सकती है एनपी ≠ सह-एनपी सममित है।

सह-एनपी पीएच (जटिलता) का एक उपसमुच्चय है, जो स्वयं पीएसपीएसीई का सबसेट है।

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

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

संदर्भ

  1. ↑ 1.0 1.1 Arora, Sanjeev; Barak, Boaz (2009). Complexity Theory: A Modern Approach. Cambridge University Press. p. 56. ISBN 978-0-521-42426-4.
  2. ↑ Hopcroft, John E. (2000). ऑटोमेटा सिद्धांत, भाषाएं और संगणना का परिचय (2nd ed.). Boston: Addison-Wesley. ISBN 0-201-44124-1. Chap. 11.
  3. ↑ Goldreich, Oded (2010). P, NP, and NP-completeness: The Basics of Computational Complexity. Cambridge University Press. p. 155. ISBN 9781139490092.


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=सह-एनपी&oldid=195698’