सह-एनपी: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, '''सह-एनपी''' एक [[जटिलता वर्ग]] है। एक [[निर्णय समस्या]] एक्स सह-एनपी का सदस्य है यदि | [[कम्प्यूटेशनल जटिलता सिद्धांत]] में, '''सह-एनपी''' एक [[जटिलता वर्ग]] है। इस प्रकार एक [[निर्णय समस्या]] एक्स सह-एनपी का सदस्य है यदि केवल इसकी [[पूरक (जटिलता)]] एक्स जटिलता वर्ग [[एनपी (जटिलता)]] में है। वर्ग को निम्नानुसार परिभाषित किया जा सकता है: इस प्रकार एक निर्णय समस्या सह-एनपी में ठीक है यदि और केवल नो-इंस्टेंस में बहुपद-लंबाई [[प्रमाणपत्र (जटिलता)]] है और बहुपद-समय एल्गोरिथ्म है जिसका उपयोग किसी भी कथित प्रमाण पत्र को सत्यापित करने के लिए किया जा सकता है। | ||
अर्थात्, 'सह-एनपी' निर्णय समस्याओं का समुच्चय है जहाँ बहुपद उपस्तिथ है पी(एन) और बहुपद-समयबद्ध [[ट्यूरिंग मशीन]] एम जैसे कि प्रत्येक उदाहरण के लिए एक्स, एक्स नो-इंस्टेंस है यदि और केवल यदि: लंबाई के कुछ संभावित प्रमाण पत्र सी के लिए पी(एन), ट्यूरिंग मशीन एम जोड़ी (एक्स, सी) को स्वीकार करती है। <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> | अर्थात्, ''''सह-एनपी'''<nowiki/>' निर्णय समस्याओं का समुच्चय है जहाँ बहुपद उपस्तिथ है पी(एन) और बहुपद-समयबद्ध [[ट्यूरिंग मशीन]] एम जैसे कि प्रत्येक उदाहरण के लिए एक्स, एक्स नो-इंस्टेंस है इस प्रकार यदि और केवल यदि: लंबाई के कुछ संभावित प्रमाण पत्र सी के लिए पी(एन), ट्यूरिंग मशीन एम जोड़ी (एक्स, सी) को स्वीकार करती है। <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> | ||
== पूरक समस्याएं == | == पूरक समस्याएं == | ||
जबकि एक एनपी समस्या पूछती है कि क्या दिया गया उदाहरण हां-उदाहरण है, इसका पूरक पूछता है कि क्या कोई उदाहरण नहीं है, जिसका अर्थ है कि पूरक सह-एनपी में है और इसके विपरीत मूल एनपी समस्या के लिए कोई भी हां-उदाहरण इसके पूरक के लिए नहीं-उदाहरण बन जाता है। | इस प्रकार जबकि एक एनपी समस्या पूछती है कि क्या दिया गया उदाहरण हां-उदाहरण है, इसका पूरक पूछता है कि क्या कोई उदाहरण नहीं है, जिसका अर्थ है कि पूरक सह-एनपी में है और इसके विपरीत मूल एनपी समस्या के लिए कोई भी हां-उदाहरण इसके पूरक के लिए नहीं-उदाहरण बन जाता है। | ||
=== असंतोष === | === असंतोष === | ||
एनपी-पूर्ण समस्या का एक उदाहरण [[बूलियन संतुष्टि समस्या]] है: एक बूलियन सूत्र दिया गया है, क्या यह संतोषजनक है (क्या कोई संभावित इनपुट है जिसके लिए सूत्र सही है)? पूरक समस्या पूछती है: बूलियन फॉर्मूला दिया गया है, क्या यह असंतोषजनक है (फॉर्मूला आउटपुट के सभी संभावित इनपुट गलत हैं)? . चूंकि यह संतुष्टि की समस्या का पूरक है, इसलिए बिना किसी उदाहरण के प्रमाण पत्र मूल एनपी समस्या से हां-उदाहरण के समान है: बूलियन वैरिएबल असाइनमेंट का सेट जो सूत्र को सत्य बनाता है। दूसरी ओर, पूरक समस्या के लिए हां-उदाहरण का प्रमाण पत्र उतना ही जटिल होगा जितना कि मूल एनपी संतुष्टि समस्या का उदाहरण नहीं है। | इस प्रकार एनपी-पूर्ण समस्या का एक उदाहरण [[बूलियन संतुष्टि समस्या]] है: एक बूलियन सूत्र दिया गया है, क्या यह संतोषजनक है (क्या कोई संभावित इनपुट है जिसके लिए सूत्र सही है)? पूरक समस्या पूछती है: बूलियन फॉर्मूला दिया गया है, क्या यह असंतोषजनक है (फॉर्मूला आउटपुट के सभी संभावित इनपुट गलत हैं)? . चूंकि यह संतुष्टि की समस्या का पूरक है, इसलिए बिना किसी उदाहरण के प्रमाण पत्र मूल एनपी समस्या से हां-उदाहरण के समान है: बूलियन वैरिएबल असाइनमेंट का सेट जो सूत्र को सत्य बनाता है। दूसरी ओर, पूरक समस्या के लिए हां-उदाहरण का प्रमाण पत्र उतना ही जटिल होगा जितना कि मूल एनपी संतुष्टि समस्या का उदाहरण नहीं है। | ||
== दोहरी समस्याएं == | == दोहरी समस्याएं == | ||
== सह-एनपी-पूर्णता == | == सह-एनपी-पूर्णता == | ||
एक समस्या एल [[सह-एनपी-पूर्ण]] है यदि और केवल यदि एल सह-एनपी में है और सह-एनपी में किसी भी समस्या के लिए, उस समस्या से एल तक बहुपद-समय की कमी उपस्तिथ है। | इस प्रकार एक समस्या एल [[सह-एनपी-पूर्ण]] है यदि और केवल यदि एल सह-एनपी में है और सह-एनपी में किसी भी समस्या के लिए, उस समस्या से एल तक बहुपद-समय की कमी उपस्तिथ है। | ||
=== टॉटोलॉजी रिडक्शन === | === टॉटोलॉजी रिडक्शन === | ||
| Line 17: | Line 17: | ||
[[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> इसे इस प्रकार दिखाया जा सकता है। मान लीजिए विरोधाभास के लिए एनपी-पूर्ण समस्या उपस्तिथ है जो सह-एनपी में है। चूंकि एनपी में सभी समस्याओं को एक्स तक कम किया जा सकता है, इस प्रकार यह है कि एनपी में हर समस्या के लिए, हम [[गैर-नियतात्मक ट्यूरिंग मशीन]] का निर्माण कर सकते हैं जो बहुपद समय में इसके पूरक का निर्णय लेती है; अर्थात इससे, यह इस प्रकार है कि एनपी में समस्याओं के पूरक का सेट सह-एनपी में समस्याओं के पूरक के सेट का सबसेट है; अर्थात, इस प्रकार सबूत है कि एनपी में कोई सह-एनपी-पूर्ण समस्या नहीं हो सकती है एनपी ≠ सह-एनपी सममित है। | ||
सह-एनपी पीएच (जटिलता) का एक उपसमुच्चय है, जो स्वयं पीएसपीएसीई का सबसेट है। | सह-एनपी पीएच (जटिलता) का एक उपसमुच्चय है, जो स्वयं पीएसपीएसीई का सबसेट है। | ||
=== पूर्णांक गुणनखंड === | === पूर्णांक गुणनखंड === | ||
एक समस्या का उदाहरण जो एनपी और सह-एनपी दोनों से संबंधित है (किन्तु पी में नहीं जाना जाता है) पूर्णांक कारककरण है: सकारात्मक पूर्णांक एम और एन दिया गया है, यह निर्धारित करें कि क्या एम का कारक एन से कम है और इससे अधिक है | इस प्रकार एक समस्या का उदाहरण जो एनपी और सह-एनपी दोनों से संबंधित है (किन्तु पी में नहीं जाना जाता है) पूर्णांक कारककरण है: सकारात्मक पूर्णांक एम और एन दिया गया है, इस प्रकार यह निर्धारित करें कि क्या एम का कारक एन से कम है और इससे अधिक है एक एनपी में सदस्यता स्पष्ट है; यदि एम में ऐसा गुणनखंड है, तो गुणनखंड स्वयं एक प्रमाण पत्र है। सह-एनपी में सदस्यता भी सीधी है: कोई केवल एम के प्रमुख कारकों को सूचीबद्ध कर सकता है, सभी अधिक या एन के बराबर, जो सत्यापनकर्ता गुणन और [[एकेएस प्रारंभिक परीक्षण]] द्वारा मान्य होने की पुष्टि कर सकता है। वर्तमान में यह ज्ञात नहीं है कि गुणनखंडन के लिए बहुपद-समय एल्गोरिथ्म है या नहीं, समतुल्य रूप से पूर्णांक गुणनखंड पी में है, और इसलिए यह उदाहरण एनपी और सह-एनपी में ज्ञात सबसे प्राकृतिक समस्याओं में से के एक रूप में दिलचस्प है, पी में हो किन्तु इसके लिए ज्ञात नहीं है। | ||
== संदर्भ == | == संदर्भ == | ||
Revision as of 10:32, 20 June 2023
कम्प्यूटेशनल जटिलता सिद्धांत में, सह-एनपी एक जटिलता वर्ग है। इस प्रकार एक निर्णय समस्या एक्स सह-एनपी का सदस्य है यदि केवल इसकी पूरक (जटिलता) एक्स जटिलता वर्ग एनपी (जटिलता) में है। वर्ग को निम्नानुसार परिभाषित किया जा सकता है: इस प्रकार एक निर्णय समस्या सह-एनपी में ठीक है यदि और केवल नो-इंस्टेंस में बहुपद-लंबाई प्रमाणपत्र (जटिलता) है और बहुपद-समय एल्गोरिथ्म है जिसका उपयोग किसी भी कथित प्रमाण पत्र को सत्यापित करने के लिए किया जा सकता है।
अर्थात्, 'सह-एनपी' निर्णय समस्याओं का समुच्चय है जहाँ बहुपद उपस्तिथ है पी(एन) और बहुपद-समयबद्ध ट्यूरिंग मशीन एम जैसे कि प्रत्येक उदाहरण के लिए एक्स, एक्स नो-इंस्टेंस है इस प्रकार यदि और केवल यदि: लंबाई के कुछ संभावित प्रमाण पत्र सी के लिए पी(एन), ट्यूरिंग मशीन एम जोड़ी (एक्स, सी) को स्वीकार करती है। [1]
पूरक समस्याएं
इस प्रकार जबकि एक एनपी समस्या पूछती है कि क्या दिया गया उदाहरण हां-उदाहरण है, इसका पूरक पूछता है कि क्या कोई उदाहरण नहीं है, जिसका अर्थ है कि पूरक सह-एनपी में है और इसके विपरीत मूल एनपी समस्या के लिए कोई भी हां-उदाहरण इसके पूरक के लिए नहीं-उदाहरण बन जाता है।
असंतोष
इस प्रकार एनपी-पूर्ण समस्या का एक उदाहरण बूलियन संतुष्टि समस्या है: एक बूलियन सूत्र दिया गया है, क्या यह संतोषजनक है (क्या कोई संभावित इनपुट है जिसके लिए सूत्र सही है)? पूरक समस्या पूछती है: बूलियन फॉर्मूला दिया गया है, क्या यह असंतोषजनक है (फॉर्मूला आउटपुट के सभी संभावित इनपुट गलत हैं)? . चूंकि यह संतुष्टि की समस्या का पूरक है, इसलिए बिना किसी उदाहरण के प्रमाण पत्र मूल एनपी समस्या से हां-उदाहरण के समान है: बूलियन वैरिएबल असाइनमेंट का सेट जो सूत्र को सत्य बनाता है। दूसरी ओर, पूरक समस्या के लिए हां-उदाहरण का प्रमाण पत्र उतना ही जटिल होगा जितना कि मूल एनपी संतुष्टि समस्या का उदाहरण नहीं है।
दोहरी समस्याएं
सह-एनपी-पूर्णता
इस प्रकार एक समस्या एल सह-एनपी-पूर्ण है यदि और केवल यदि एल सह-एनपी में है और सह-एनपी में किसी भी समस्या के लिए, उस समस्या से एल तक बहुपद-समय की कमी उपस्तिथ है।
टॉटोलॉजी रिडक्शन
यह निर्धारित करना कि क्या प्रस्तावपरक तर्क में सूत्र एक पुनरुक्ति है, सह-एनपी-पूर्ण है: अर्थात, यदि सूत्र अपने चरों के लिए हर संभव असाइनमेंट के अनुसार सही का मूल्यांकन करता है।[1]
अन्य वर्गों से संबंध
पी (जटिलता), बहुपद समय हल करने योग्य समस्याओं का वर्ग, एनपी और सह-एनपी दोनों का सबसेट है। पी को दोनों स्थितियों में सख्त उपसमुच्चय माना जाता है (और स्पष्ट रूप से स्थिति में सख्त नहीं हो सकता है और दूसरे में सख्त नहीं है)।
एनपी और सह-एनपी को भी असमान माना जाता है।[2] इस प्रकार यदि ऐसा है, तो कोई एनपी-पूर्ण समस्या सह-एनपी में नहीं हो सकती है और कोई सह-एनपी-पूर्ण समस्या एनपी में नहीं हो सकती है।[3] इसे इस प्रकार दिखाया जा सकता है। मान लीजिए विरोधाभास के लिए एनपी-पूर्ण समस्या उपस्तिथ है जो सह-एनपी में है। चूंकि एनपी में सभी समस्याओं को एक्स तक कम किया जा सकता है, इस प्रकार यह है कि एनपी में हर समस्या के लिए, हम गैर-नियतात्मक ट्यूरिंग मशीन का निर्माण कर सकते हैं जो बहुपद समय में इसके पूरक का निर्णय लेती है; अर्थात इससे, यह इस प्रकार है कि एनपी में समस्याओं के पूरक का सेट सह-एनपी में समस्याओं के पूरक के सेट का सबसेट है; अर्थात, इस प्रकार सबूत है कि एनपी में कोई सह-एनपी-पूर्ण समस्या नहीं हो सकती है एनपी ≠ सह-एनपी सममित है।
सह-एनपी पीएच (जटिलता) का एक उपसमुच्चय है, जो स्वयं पीएसपीएसीई का सबसेट है।
पूर्णांक गुणनखंड
इस प्रकार एक समस्या का उदाहरण जो एनपी और सह-एनपी दोनों से संबंधित है (किन्तु पी में नहीं जाना जाता है) पूर्णांक कारककरण है: सकारात्मक पूर्णांक एम और एन दिया गया है, इस प्रकार यह निर्धारित करें कि क्या एम का कारक एन से कम है और इससे अधिक है एक एनपी में सदस्यता स्पष्ट है; यदि एम में ऐसा गुणनखंड है, तो गुणनखंड स्वयं एक प्रमाण पत्र है। सह-एनपी में सदस्यता भी सीधी है: कोई केवल एम के प्रमुख कारकों को सूचीबद्ध कर सकता है, सभी अधिक या एन के बराबर, जो सत्यापनकर्ता गुणन और एकेएस प्रारंभिक परीक्षण द्वारा मान्य होने की पुष्टि कर सकता है। वर्तमान में यह ज्ञात नहीं है कि गुणनखंडन के लिए बहुपद-समय एल्गोरिथ्म है या नहीं, समतुल्य रूप से पूर्णांक गुणनखंड पी में है, और इसलिए यह उदाहरण एनपी और सह-एनपी में ज्ञात सबसे प्राकृतिक समस्याओं में से के एक रूप में दिलचस्प है, पी में हो किन्तु इसके लिए ज्ञात नहीं है।
संदर्भ
- ↑ 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.
- ↑ Hopcroft, John E. (2000). ऑटोमेटा सिद्धांत, भाषाएं और संगणना का परिचय (2nd ed.). Boston: Addison-Wesley. ISBN 0-201-44124-1. Chap. 11.
- ↑ Goldreich, Oded (2010). P, NP, and NP-completeness: The Basics of Computational Complexity. Cambridge University Press. p. 155. ISBN 9781139490092.
