सह-एनपी: Difference between revisions

Revision as of 20:37, 19 June 2023

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)$ .^[1]

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

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

असंतोष

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

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

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

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

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

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

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

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

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

एनपी और सह-एनपी को भी असमान माना जाता है।^[2] यदि ऐसा है, तो कोई एनपी-पूर्ण समस्या सह-एनपी में नहीं हो सकती है और कोई सह-एनपी-पूर्ण समस्या एनपी में नहीं हो सकती है।^[3] इसे इस प्रकार दिखाया जा सकता है। मान लीजिए विरोधाभास के लिए एनपी-पूर्ण समस्या उपस्तिथ है 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 का सबसेट है।

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

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

संदर्भ

↑ ^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.

बाहरी संबंध

Complexity Zoo: coNP

[A&B-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.

[1]

[2]

[3]

@@ Line 1: / Line 1: @@
 {{unsolved|computer science|{{tmath|1=\textsf{NP}\ \overset{?}{=}\ \textsf{co-NP} }} }}
-[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, सह-एनपी [[जटिलता वर्ग]] है। [[निर्णय समस्या]] एक्स सह-एनपी का सदस्य है अगर और केवल अगर इसकी [[पूरक (जटिलता)]] {{overline|X}} जटिलता वर्ग [[एनपी (जटिलता)]] में है। वर्ग को निम्नानुसार परिभाषित किया जा सकता है: निर्णय समस्या सह-एनपी में ठीक है यदि केवल नो-इंस्टेंस में बहुपद-लंबाई [[प्रमाणपत्र (जटिलता)]] है और बहुपद-समय एल्गोरिथ्म है जिसका उपयोग किसी भी कथित प्रमाण पत्र को सत्यापित करने के लिए किया जा सकता है।
+[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, सह-एनपी [[जटिलता वर्ग]] है। [[निर्णय समस्या]] एक्स सह-एनपी का सदस्य है यदि और केवल यदि इसकी [[पूरक (जटिलता)]] {{overline|X}} जटिलता वर्ग [[एनपी (जटिलता)]] में है। वर्ग को निम्नानुसार परिभाषित किया जा सकता है: निर्णय समस्या सह-एनपी में ठीक है यदि केवल नो-इंस्टेंस में बहुपद-लंबाई [[प्रमाणपत्र (जटिलता)]] है और बहुपद-समय एल्गोरिथ्म है जिसका उपयोग किसी भी कथित प्रमाण पत्र को सत्यापित करने के लिए किया जा सकता है।
-अर्थात्, 'co-NP' निर्णय समस्याओं का समुच्चय है जहाँ बहुपद मौजूद है {{tmath|p(n)}} और बहुपद-समयबद्ध [[ट्यूरिंग मशीन]] एम जैसे कि प्रत्येक उदाहरण के लिए एक्स, एक्स नो-इंस्टेंस है अगर और केवल अगर: लंबाई के कुछ संभावित प्रमाण पत्र सी के लिए {{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>
+अर्थात्, 'co-NP' निर्णय समस्याओं का समुच्चय है जहाँ बहुपद उपस्तिथ है {{tmath|p(n)}} और बहुपद-समयबद्ध [[ट्यूरिंग मशीन]] एम जैसे कि प्रत्येक उदाहरण के लिए एक्स, एक्स नो-इंस्टेंस है यदि और केवल यदि: लंबाई के कुछ संभावित प्रमाण पत्र सी के लिए {{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>
 == पूरक समस्याएं ==
 {{main|Complement (complexity)}}
@@ Line 15: / Line 15: @@
 == सह-एनपी-पूर्णता ==
 {{main|co-NP-complete}}
-समस्या एल [[सह-एनपी-पूर्ण]] है अगर और केवल अगर एल सह-एनपी में है और सह-एनपी में किसी भी समस्या के लिए, उस समस्या से एल तक बहुपद-समय की कमी मौजूद है।
+समस्या एल [[सह-एनपी-पूर्ण]] है यदि और केवल यदि एल सह-एनपी में है और सह-एनपी में किसी भी समस्या के लिए, उस समस्या से एल तक बहुपद-समय की कमी उपस्तिथ है।
 === टॉटोलॉजी रिडक्शन ===
-यह निर्धारित करना कि क्या प्रस्तावपरक तर्क में सूत्र तनातनी (तर्क) है, सह-एनपी-पूर्ण है: अर्थात, यदि सूत्र अपने चर के लिए हर संभव असाइनमेंट के तहत सही का मूल्यांकन करता है।<ref name="A&B"/>
+यह निर्धारित करना कि क्या प्रस्तावपरक तर्क में सूत्र तनातनी (तर्क) है, सह-एनपी-पूर्ण है: अर्थात, यदि सूत्र अपने चर के लिए हर संभव असाइनमेंट के अनुसार सही का मूल्यांकन करता है।<ref name="A&B"/>
 == अन्य वर्गों से संबंध ==
 {{further|Complexity class}}
-[[Image:Complexity-classes-polynomial.svg|thumb|[[पी (जटिलता)]], एनपी (जटिलता), सह-एनपी, [[बीपीपी (जटिलता)]], पी/पॉली, [[पीएच (जटिलता)]], और [[पीएसपीएसीई]] सहित जटिलता वर्गों का समावेश]]पी (जटिलता), बहुपद समय हल करने योग्य समस्याओं का वर्ग, एनपी और सह-एनपी दोनों का सबसेट है। P को दोनों मामलों में सख्त उपसमुच्चय माना जाता है (और स्पष्ट रूप से मामले में सख्त नहीं हो सकता है और दूसरे में सख्त नहीं है)।
+[[Image:Complexity-classes-polynomial.svg|thumb|[[पी (जटिलता)]], एनपी (जटिलता), सह-एनपी, [[बीपीपी (जटिलता)]], पी/पॉली, [[पीएच (जटिलता)]], और [[पीएसपीएसीई]] सहित जटिलता वर्गों का समावेश]]पी (जटिलता), बहुपद समय हल करने योग्य समस्याओं का वर्ग, एनपी और सह-एनपी दोनों का सबसेट है। P को दोनों स्थितियों में सख्त उपसमुच्चय माना जाता है (और स्पष्ट रूप से स्थिति में सख्त नहीं हो सकता है और दूसरे में सख्त नहीं है)।
-एनपी और सह-एनपी को भी असमान माना जाता है।<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} }} सममित है।
+एनपी और सह-एनपी को भी असमान माना जाता है।<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} }} सममित है।
 सह-एनपी PH (जटिलता) का सबसेट है, जो स्वयं PSPACE का सबसेट है।
@@ Line 30: / Line 30: @@
 === पूर्णांक गुणनखंड ===
 {{main|Integer factorization}}
-समस्या का उदाहरण जो एनपी और सह-एनपी दोनों से संबंधित है (लेकिन पी में नहीं जाना जाता है) Integer_factorization#Difficulty_and_complexity है: सकारात्मक पूर्णांक m और n दिया गया है, यह निर्धारित करें कि क्या m का कारक n से कम है और इससे अधिक है एक। एनपी में सदस्यता स्पष्ट है; यदि m में ऐसा गुणनखंड है, तो गुणनखंड स्वयं प्रमाण पत्र है। सह-एनपी में सदस्यता भी सीधी है: कोई केवल एम के प्रमुख कारकों को सूचीबद्ध कर सकता है, सभी अधिक या एन के बराबर, जो सत्यापनकर्ता गुणन और [[एकेएस प्रारंभिक परीक्षण]] द्वारा मान्य होने की पुष्टि कर सकता है। वर्तमान में यह ज्ञात नहीं है कि गुणनखंडन के लिए बहुपद-समय एल्गोरिथ्म है या नहीं, समतुल्य रूप से पूर्णांक गुणनखंड P में है, और इसलिए यह उदाहरण एनपी और सह-एनपी में ज्ञात सबसे प्राकृतिक समस्याओं में से के रूप में दिलचस्प है, लेकिन इसके लिए ज्ञात नहीं है। पी में हो
+समस्या का उदाहरण जो एनपी और सह-एनपी दोनों से संबंधित है (किन्तु पी में नहीं जाना जाता है) Integer_factorization#Difficulty_and_complexity है: सकारात्मक पूर्णांक m और n दिया गया है, यह निर्धारित करें कि क्या m का कारक n से कम है और इससे अधिक है एक। एनपी में सदस्यता स्पष्ट है; यदि m में ऐसा गुणनखंड है, तो गुणनखंड स्वयं प्रमाण पत्र है। सह-एनपी में सदस्यता भी सीधी है: कोई केवल एम के प्रमुख कारकों को सूचीबद्ध कर सकता है, सभी अधिक या एन के बराबर, जो सत्यापनकर्ता गुणन और [[एकेएस प्रारंभिक परीक्षण]] द्वारा मान्य होने की पुष्टि कर सकता है। वर्तमान में यह ज्ञात नहीं है कि गुणनखंडन के लिए बहुपद-समय एल्गोरिथ्म है या नहीं, समतुल्य रूप से पूर्णांक गुणनखंड P में है, और इसलिए यह उदाहरण एनपी और सह-एनपी में ज्ञात सबसे प्राकृतिक समस्याओं में से के रूप में रोचक है, किन्तु इसके लिए ज्ञात नहीं है। पी में हो
 == संदर्भ ==

v t e Important complexity classes (more)
Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP APX FP
Suspected infeasible	UP NP NP-complete NP-hard co-NP co-NP-complete AM QMA PH ⊕P PP #P #P-complete IP PSPACE PSPACE-complete
Considered infeasible	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY PR R RE ALL
Class hierarchies	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetical hierarchy Boolean hierarchy
Families of classes	DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system

Anonymous

Search

सह-एनपी: Difference between revisions

Namespaces

More

Page actions

Revision as of 20:37, 19 June 2023

Contents