सह-एनपी - Revision history

Manidh at 14:45, 23 June 2023

2023-06-23T14:45:14Z

← Older revision		Revision as of 20:15, 23 June 2023
Line 31:		Line 31:
	{{ComplexityClasses}}		{{ComplexityClasses}}

	{{DEFAULTSORT:Co-Np}}~~[[Category: जटिलता वर्ग]]~~		{{DEFAULTSORT:Co-Np}}

			[[Category:Collapse templates\|Co-Np]]
			[[Category:Created On 08/06/2023\|Co-Np]]
	[[Category: ~~Machine Translated Page~~]]		[[Category:Machine Translated Page\|Co-Np]]
	[[Category:Created On 08/06/2023]]		[[Category:Navigational boxes\| ]]
	[[Category:Vigyan Ready]]		[[Category:Navigational boxes without horizontal lists\|Co-Np]]
			[[Category:Pages with script errors\|Co-Np]]
			[[Category:Sidebars with styles needing conversion\|Co-Np]]
			[[Category:Template documentation pages\|Documentation/doc]]
			[[Category:Templates Vigyan Ready]]
			[[Category:Templates generating microformats\|Co-Np]]
			[[Category:Templates that are not mobile friendly\|Co-Np]]
			[[Category:Templates using TemplateData\|Co-Np]]
			[[Category:Wikipedia metatemplates\|Co-Np]]
			[[Category:जटिलता वर्ग\|Co-Np]]

Indicwiki: 9 revisions imported from :alpha:सह-एनपी

2023-06-23T11:03:05Z

9 revisions imported from alpha:सह-एनपी

← Older revision	Revision as of 16:33, 23 June 2023
(No difference)

alpha>Neeraja: added Category:Vigyan Ready using HotCat

2023-06-22T08:01:38Z

added Category:Vigyan Ready using HotCat

← Older revision		Revision as of 13:31, 22 June 2023
Line 37:		Line 37:
	[[Category: Machine Translated Page]]		[[Category: Machine Translated Page]]
	[[Category:Created On 08/06/2023]]		[[Category:Created On 08/06/2023]]
			[[Category:Vigyan Ready]]

alpha>Ajays at 07:24, 20 June 2023

2023-06-20T07:24:24Z

← Older revision		Revision as of 12:54, 20 June 2023
Line 1:		Line 1:
	[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, '''सह-एनपी''' एक [[जटिलता वर्ग]] है। इस प्रकार एक [[निर्णय समस्या]] एक्स सह-एनपी का सदस्य है यदि केवल इसकी [[पूरक (जटिलता)]] एक्स जटिलता वर्ग [[एनपी (जटिलता)]] में है। वर्ग को निम्नानुसार परिभाषित किया जा सकता है: इस प्रकार एक निर्णय समस्या सह-एनपी में ठीक है यदि और केवल नो-इंस्टेंस में बहुपद-लंबाई [[प्रमाणपत्र (जटिलता)]] है और बहुपद-समय एल्गोरिथ्म है जिसका उपयोग किसी भी कथित प्रमाण पत्र को सत्यापित करने के लिए किया जा सकता है।		[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, '''सह-एनपी''' एक [[जटिलता वर्ग]] है। इस प्रकार एक [[निर्णय समस्या]] एक्स सह-एनपी का सदस्य है यदि केवल इसकी [[पूरक (जटिलता)]] एक्स जटिलता वर्ग [[एनपी (जटिलता)]] में है। वर्ग को निम्नानुसार परिभाषित किया जा सकता है: इस प्रकार एक निर्णय समस्या सह-एनपी में ठीक है यदि और केवल नो-इंस्टेंस में बहुपद-लंबाई [[प्रमाणपत्र (जटिलता)]] है और बहुपद-समय एल्गोरिथ्म है जिसका उपयोग किसी भी कथित प्रमाण पत्र को सत्यापित करने के लिए किया जा सकता है।

	अर्थात्, ''''सह-एनपी'''<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>		अर्थात्, ''''सह-एनपी'''<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 26:		Line 26:
	== संदर्भ ==		== संदर्भ ==
	{{Reflist}}		{{Reflist}}


	== बाहरी संबंध ==		== बाहरी संबंध ==
	* {{CZoo\|coNP\|C#conp}}		* {{CZoo\|coNP\|C#conp}}

alpha>Ajays at 05:02, 20 June 2023

2023-06-20T05:02:54Z

← Older revision		Revision as of 10:32, 20 June 2023
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> इसे इस प्रकार दिखाया जा सकता है। मान लीजिए विरोधाभास के लिए एनपी-पूर्ण समस्या उपस्तिथ है जो सह-एनपी में है। चूंकि एनपी में सभी समस्याओं को एक्स तक कम किया जा सकता है, इस प्रकार यह है कि एनपी में हर समस्या के लिए, हम [[गैर-नियतात्मक ट्यूरिंग मशीन]] का निर्माण कर सकते हैं जो बहुपद समय में इसके पूरक का निर्णय लेती है; अर्थात इससे, यह इस प्रकार है कि एनपी में समस्याओं के पूरक का सेट सह-एनपी में समस्याओं के पूरक के सेट का सबसेट है; अर्थात, इस प्रकार सबूत है कि एनपी में कोई सह-एनपी-पूर्ण समस्या नहीं हो सकती है एनपी ≠ सह-एनपी सममित है।

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

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

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

alpha>Ajays at 17:16, 19 June 2023

2023-06-19T17:16:20Z

Show changes

alpha>Ajays at 16:55, 19 June 2023

2023-06-19T16:55:55Z

Show changes

alpha>Ajays at 16:09, 19 June 2023

2023-06-19T16:09:54Z

← Older revision		Revision as of 21:39, 19 June 2023
Line 1:		Line 1:
	{{unsolved\|computer science\|{{tmath\|1=\textsf{NP}\ \overset{?}{=}\ \textsf{co-NP} }} }}		{{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~~)}}		{{main\|पूरक (जटिलता)}}
	जबकि एनपी समस्या पूछती है कि क्या दिया गया उदाहरण हां-उदाहरण है, इसका पूरक पूछता है कि क्या कोई उदाहरण नहीं है, जिसका अर्थ है कि पूरक सह-एनपी में है। मूल एनपी समस्या के लिए कोई भी हां-उदाहरण इसके पूरक के लिए नहीं-उदाहरण बन जाता है, और इसके विपरीत।		जबकि एनपी समस्या पूछती है कि क्या दिया गया उदाहरण हां-उदाहरण है, इसका पूरक पूछता है कि क्या कोई उदाहरण नहीं है, जिसका अर्थ है कि पूरक सह-एनपी में है। मूल एनपी समस्या के लिए कोई भी हां-उदाहरण इसके पूरक के लिए नहीं-उदाहरण बन जाता है, और इसके विपरीत।

alpha>Ajays at 15:07, 19 June 2023

2023-06-19T15:07:35Z

← Older revision		Revision as of 20:37, 19 June 2023
Line 1:		Line 1:
	{{unsolved\|computer science\|{{tmath\|1=\textsf{NP}\ \overset{?}{=}\ \textsf{co-NP} }} }}		{{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)}}		{{main\|Complement (complexity)}}
Line 15:		Line 15:
	== सह-एनपी-पूर्णता ==		== सह-एनपी-पूर्णता ==
	{{main\|co-NP-complete}}		{{main\|co-NP-complete}}
	समस्या एल [[सह-एनपी-पूर्ण]] है ~~अगर~~ और केवल ~~अगर~~ एल सह-एनपी में है और सह-एनपी में किसी भी समस्या के लिए, उस समस्या से एल तक बहुपद-समय की कमी ~~मौजूद~~ है।		समस्या एल [[सह-एनपी-पूर्ण]] है यदि और केवल यदि एल सह-एनपी में है और सह-एनपी में किसी भी समस्या के लिए, उस समस्या से एल तक बहुपद-समय की कमी उपस्तिथ है।

	=== टॉटोलॉजी रिडक्शन ===		=== टॉटोलॉजी रिडक्शन ===
	यह निर्धारित करना कि क्या प्रस्तावपरक तर्क में सूत्र तनातनी (तर्क) है, सह-एनपी-पूर्ण है: अर्थात, यदि सूत्र अपने चर के लिए हर संभव असाइनमेंट के ~~तहत~~ सही का मूल्यांकन करता है।<ref name="A&B"/>		यह निर्धारित करना कि क्या प्रस्तावपरक तर्क में सूत्र तनातनी (तर्क) है, सह-एनपी-पूर्ण है: अर्थात, यदि सूत्र अपने चर के लिए हर संभव असाइनमेंट के अनुसार सही का मूल्यांकन करता है।<ref name="A&B"/>
	== अन्य वर्गों से संबंध ==		== अन्य वर्गों से संबंध ==
	{{further\|Complexity class}}		{{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 का सबसेट है।		सह-एनपी PH (जटिलता) का सबसेट है, जो स्वयं PSPACE का सबसेट है।
Line 30:		Line 30:
	=== पूर्णांक गुणनखंड ===		=== पूर्णांक गुणनखंड ===
	{{main\|Integer factorization}}		{{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 में है, और इसलिए यह उदाहरण एनपी और सह-एनपी में ज्ञात सबसे प्राकृतिक समस्याओं में से के रूप में रोचक है, किन्तु इसके लिए ज्ञात नहीं है। पी में हो

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

alpha>Ajays at 14:51, 19 June 2023

2023-06-19T14:51:42Z

← Older revision		Revision as of 20:21, 19 June 2023
Line 1:		Line 1:
	~~{{lowercase}}~~
	{{unsolved\|computer science\|{{tmath\|1=\textsf{NP}\ \overset{?}{=}\ \textsf{co-NP} }} }}		{{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)}}		{{main\|Complement (complexity)}}
	जबकि एक एनपी समस्या पूछती है कि क्या दिया गया उदाहरण हां-उदाहरण है, इसका पूरक पूछता है कि क्या कोई उदाहरण नहीं है, जिसका अर्थ है कि पूरक सह-एनपी में है। मूल एनपी समस्या के लिए कोई भी हां-उदाहरण इसके पूरक के लिए नहीं-उदाहरण बन जाता है, और इसके विपरीत।		जबकि एनपी समस्या पूछती है कि क्या दिया गया उदाहरण हां-उदाहरण है, इसका पूरक पूछता है कि क्या कोई उदाहरण नहीं है, जिसका अर्थ है कि पूरक सह-एनपी में है। मूल एनपी समस्या के लिए कोई भी हां-उदाहरण इसके पूरक के लिए नहीं-उदाहरण बन जाता है, और इसके विपरीत।

	=== असंतोष ===		=== असंतोष ===
	{{further\|Unsatisfiable core}}		{{further\|Unsatisfiable core}}
	एनपी-पूर्ण समस्या का एक उदाहरण [[बूलियन संतुष्टि समस्या]] है: एक बूलियन सूत्र दिया गया है, क्या यह संतोषजनक है (क्या कोई संभावित इनपुट है जिसके लिए सूत्र सही है)? पूरक समस्या पूछती है: एक बूलियन फॉर्मूला दिया गया है, क्या यह असंतोषजनक है (फॉर्मूला आउटपुट के सभी संभावित इनपुट गलत हैं)? . चूंकि यह संतुष्टि की समस्या का पूरक है, इसलिए बिना किसी उदाहरण के प्रमाण पत्र मूल एनपी समस्या से हां-उदाहरण के समान है: बूलियन वैरिएबल असाइनमेंट का एक सेट जो सूत्र को सत्य बनाता है। दूसरी ओर, पूरक समस्या के लिए हां-उदाहरण का प्रमाण पत्र उतना ही जटिल होगा जितना कि मूल एनपी संतुष्टि समस्या का उदाहरण नहीं।~~{{clarify\|reason=how complex is such a certificate?\|date=June 2021}}~~		एनपी-पूर्ण समस्या का उदाहरण [[बूलियन संतुष्टि समस्या]] है: बूलियन सूत्र दिया गया है, क्या यह संतोषजनक है (क्या कोई संभावित इनपुट है जिसके लिए सूत्र सही है)? पूरक समस्या पूछती है: बूलियन फॉर्मूला दिया गया है, क्या यह असंतोषजनक है (फॉर्मूला आउटपुट के सभी संभावित इनपुट गलत हैं)? . चूंकि यह संतुष्टि की समस्या का पूरक है, इसलिए बिना किसी उदाहरण के प्रमाण पत्र मूल एनपी समस्या से हां-उदाहरण के समान है: बूलियन वैरिएबल असाइनमेंट का सेट जो सूत्र को सत्य बनाता है। दूसरी ओर, पूरक समस्या के लिए हां-उदाहरण का प्रमाण पत्र उतना ही जटिल होगा जितना कि मूल एनपी संतुष्टि समस्या का उदाहरण नहीं।

	== दोहरी समस्याएं ==		== दोहरी समस्याएं ==
	{{main\|Duality (optimization)}}		{{main\|Duality (optimization)}}
	~~{{expand section\|with=examples of duals for decision/optimization problems in NP and co-NP\|date=June 2021}}~~

	== सह-एनपी-पूर्णता ==		== सह-एनपी-पूर्णता ==
	{{main\|co-NP-complete}}		{{main\|co-NP-complete}}
	एक समस्या एल [[सह-एनपी-पूर्ण]] है अगर और केवल अगर एल सह-एनपी में है और सह-एनपी में किसी भी समस्या के लिए, उस समस्या से एल तक बहुपद-समय की कमी मौजूद है।		समस्या एल [[सह-एनपी-पूर्ण]] है अगर और केवल अगर एल सह-एनपी में है और सह-एनपी में किसी भी समस्या के लिए, उस समस्या से एल तक बहुपद-समय की कमी मौजूद है।

	=== टॉटोलॉजी रिडक्शन ===		=== टॉटोलॉजी रिडक्शन ===
	यह निर्धारित करना कि क्या प्रस्तावपरक तर्क में एक सूत्र एक तनातनी (तर्क) है, सह-एनपी-पूर्ण है: अर्थात, यदि सूत्र अपने चर के लिए हर संभव असाइनमेंट के तहत सही का मूल्यांकन करता है।<ref name="A&B"/>		यह निर्धारित करना कि क्या प्रस्तावपरक तर्क में सूत्र तनातनी (तर्क) है, सह-एनपी-पूर्ण है: अर्थात, यदि सूत्र अपने चर के लिए हर संभव असाइनमेंट के तहत सही का मूल्यांकन करता है।<ref name="A&B"/>


	== अन्य वर्गों से संबंध ==		== अन्य वर्गों से संबंध ==
	{{further\|Complexity class}}		{{further\|Complexity class}}

	[[Image:Complexity-classes-polynomial.svg\|thumb\|[[पी (जटिलता)]], एनपी (जटिलता), सह-एनपी, [[बीपीपी (जटिलता)]], पी/पॉली, [[पीएच (जटिलता)]], और [[पीएसपीएसीई]] सहित जटिलता वर्गों का समावेश]]पी (जटिलता), बहुपद समय हल करने योग्य समस्याओं का वर्ग, एनपी और सह-एनपी दोनों का एक सबसेट है। P को दोनों मामलों में एक सख्त उपसमुच्चय माना जाता है (और स्पष्ट रूप से एक मामले में सख्त नहीं हो सकता है और दूसरे में सख्त नहीं है)।~~{{citation needed\|date=June 2021}}~~		[[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 का एक सबसेट है।		सह-एनपी PH (जटिलता) का सबसेट है, जो स्वयं PSPACE का सबसेट है।

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

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

← Older revision		Revision as of 20:15, 23 June 2023
Line 31:		Line 31:
	{{ComplexityClasses}}		{{ComplexityClasses}}

	{{DEFAULTSORT:Co-Np}}~~[[Category: जटिलता वर्ग]]~~		{{DEFAULTSORT:Co-Np}}

			[[Category:Collapse templates\|Co-Np]]
			[[Category:Created On 08/06/2023\|Co-Np]]
	[[Category: ~~Machine Translated Page~~]]		[[Category:Machine Translated Page\|Co-Np]]
	[[Category:Created On 08/06/2023]]		[[Category:Navigational boxes\| ]]
	[[Category:Vigyan Ready]]		[[Category:Navigational boxes without horizontal lists\|Co-Np]]
			[[Category:Pages with script errors\|Co-Np]]
			[[Category:Sidebars with styles needing conversion\|Co-Np]]
			[[Category:Template documentation pages\|Documentation/doc]]
			[[Category:Templates Vigyan Ready]]
			[[Category:Templates generating microformats\|Co-Np]]
			[[Category:Templates that are not mobile friendly\|Co-Np]]
			[[Category:Templates using TemplateData\|Co-Np]]
			[[Category:Wikipedia metatemplates\|Co-Np]]
			[[Category:जटिलता वर्ग\|Co-Np]]