बहुपद-समय में कमी: Difference between revisions
No edit summary |
No edit summary |
||
| (6 intermediate revisions by 3 users not shown) | |||
| Line 10: | Line 10: | ||
</ref> | </ref> | ||
एक बहुपद-समय में कमी यह सिद्ध करती है कि पहली समस्या दूसरी समस्या से अधिक कठिन नहीं है क्योंकि जब भी दूसरी समस्या के लिए एक कुशल [[कलन विधि]] उपस्थित होता है तो पहली समस्या के लिए भी उपस्थित होता है। विरोधाभास से यदि पहली समस्या के लिए कोई कुशल एल्गोरिदम उपस्थित नहीं है तो दूसरे के लिए भी कोई अस्तित्व नहीं है।<ref name="kleinberg-tardos" /> [[जटिलता वर्ग]] और उन वर्गों के लिए पूर्ण समस्याओं दोनों को परिभाषित करने के लिए बहुपद-समय की | एक बहुपद-समय में कमी यह सिद्ध करती है कि पहली समस्या दूसरी समस्या से अधिक कठिन नहीं है क्योंकि जब भी दूसरी समस्या के लिए एक कुशल [[कलन विधि]] उपस्थित होता है तो पहली समस्या के लिए भी उपस्थित होता है। विरोधाभास से यदि पहली समस्या के लिए कोई कुशल एल्गोरिदम उपस्थित नहीं है तो दूसरे के लिए भी कोई अस्तित्व नहीं है।<ref name="kleinberg-tardos" /> [[जटिलता वर्ग]] और उन वर्गों के लिए पूर्ण समस्याओं दोनों को परिभाषित करने के लिए बहुपद-समय की अल्पीकरण अधिकांशतः जटिलता सिद्धांत में उपयोग की जाती है। | ||
== अल्पीकरण के प्रकार == | == अल्पीकरण के प्रकार == | ||
तीन सबसे सामान्य प्रकार के बहुपद-समय में कमी सबसे कम से कम प्रतिबंधात्मक बहुपद-समय में कई-एक अल्पीकरण सत्य-तालिका में कमी और ट्यूरिंग अल्पीकरण हैं। इनमें से सबसे अधिक बार उपयोग किए जाने वाले कई-एक | तीन सबसे सामान्य प्रकार के बहुपद-समय में कमी सबसे कम से कम प्रतिबंधात्मक बहुपद-समय में कई-एक अल्पीकरण सत्य-तालिका में कमी और ट्यूरिंग अल्पीकरण हैं। इनमें से सबसे अधिक बार उपयोग किए जाने वाले कई-एक अल्पीकरण हैं, और कुछ स्थिति में वाक्यांश बहुपद-समय में कमी का अर्थ बहुपद-समय में कई-एक कमी के लिए किया जा सकता है।<ref>{{citation|title=Complexity Theory: Exploring the Limits of Efficient Algorithms|first=Ingo|last=Wegener|authorlink=Ingo Wegener|page=60|publisher=Springer|year=2005|isbn=9783540274773}}.</ref> सबसे सामान्य अल्पीकरण ट्यूरिंग अल्पीकरण हैं और सबसे अधिक प्रतिबंधक कई-एक अल्पीकरण हैं जिनके बीच में जगह घेरने वाली सत्य-तालिका अल्पीकरण होती है।<ref name="mandal2014">{{cite conference|first1=Debasis|last1=Mandal|first2=A.|last2=Pavan|first3=Rajeswari|last3=Venugopalan|title=वर्स्ट-केस कठोरता परिकल्पना के तहत कार्प-लेविन पूर्णता से कुक पूर्णता को अलग करना|year=2014|url=http://drops.dagstuhl.de/opus/volltexte/2014/4862/|conference=34th International Conference on Foundation of Software Technology and Theoretical Computer Science|isbn=978-3-939897-77-4}}</ref> | ||
=== अनेक-एक | === अनेक-एक अल्पीकरण === | ||
समस्या A से समस्या B तक एक बहुपद-समय कई-एक कमी (दोनों जिनमें सामान्यतः निर्णय की समस्या होने की आवश्यकता होती है) एक बहुपद-समय एल्गोरिथ्म है जो इनपुट को समस्या A से समस्या B में इनपुट में बदलने के लिए है जैसे कि रूपांतरित समस्या का आउटपुट मूल समस्या के समान होता है। समस्या A का एक उदाहरण x समस्या B का एक उदाहरण y उत्पन्न करने के लिए इस परिवर्तन को प्रयुक्त करके हल किया जा सकता है समस्या B के लिए एक एल्गोरिथम के इनपुट के रूप में y दे रहा है और इसके आउटपुट को वापस कर रहा है। बहुपद-समय कई-एक | समस्या A से समस्या B तक एक बहुपद-समय कई-एक कमी (दोनों जिनमें सामान्यतः निर्णय की समस्या होने की आवश्यकता होती है) एक बहुपद-समय एल्गोरिथ्म है जो इनपुट को समस्या A से समस्या B में इनपुट में बदलने के लिए है जैसे कि रूपांतरित समस्या का आउटपुट मूल समस्या के समान होता है। समस्या A का एक उदाहरण x समस्या B का एक उदाहरण y उत्पन्न करने के लिए इस परिवर्तन को प्रयुक्त करके हल किया जा सकता है समस्या B के लिए एक एल्गोरिथम के इनपुट के रूप में y दे रहा है और इसके आउटपुट को वापस कर रहा है। बहुपद-समय कई-एक अल्पीकरण को [[रिचर्ड कार्प]] के नाम पर 'बहुपद परिवर्तन' या 'कार्प अल्पीकरण' के रूप में भी जाना जा सकता है। इस प्रकार की कमी को <math>A \le_m^P B</math> या <math>A \le_p B</math> द्वारा निरूपित किया जाता है।.<ref name="goldreich">{{citation|title=Computational Complexity: A Conceptual Perspective|first=Oded|last=Goldreich|authorlink=Oded Goldreich|publisher=Cambridge University Press|year=2008|isbn=9781139472746|pages=59–60}}</ref><ref name = "kleinberg-tardos"/> | ||
===सत्य तालिका में कमी === | ===सत्य तालिका में कमी === | ||
समस्या ''A'' से समस्या ''B'' | समस्या ''A'' से समस्या ''B'' (दोनों निर्णय समस्याएं) में एक बहुपद-समय की सत्य-सारणी में कमी एक बहुपद समय एल्गोरिदम है जो इनपुट को समस्या ''A'' में इनपुट की एक निश्चित संख्या में समस्या ''B'' में बदलने के लिए है, जैसे कि मूल समस्या के लिए आउटपुट ''B'' के लिए आउटपुट के एक फलन के रूप में व्यक्त किया जा सकता है। ''A'' के लिए आउटपुट में ''B'' के लिए आउटपुट मैप करने वाला फलन सभी इनपुट के लिए समान होना चाहिए जिससे इसे सत्य तालिका द्वारा व्यक्त किया जा सकता है । इस प्रकार की कमी को अभिव्यक्ति <math>A \le_{tt}^P B</math> द्वारा निरूपित किया जा सकता है .<ref>{{citation | ||
| last1 = Buss | first1 = S.R. | author1-link = Samuel Buss | | last1 = Buss | first1 = S.R. | author1-link = Samuel Buss | ||
| last2 = Hay | first2 = L. | | last2 = Hay | first2 = L. | ||
| Line 29: | Line 29: | ||
| year = 1988| isbn = 978-0-8186-0866-7 | citeseerx = 10.1.1.5.2387 }}.</ref> | | year = 1988| isbn = 978-0-8186-0866-7 | citeseerx = 10.1.1.5.2387 }}.</ref> | ||
=== ट्यूरिंग अल्पीकरण === | === ट्यूरिंग अल्पीकरण === | ||
एक समस्या ''A'' से एक समस्या ''B'' तक एक बहुपद-समय ट्यूरिंग कमी एक एल्गोरिदम है जो समस्या ''B'' | एक समस्या ''A'' से एक समस्या ''B'' तक एक बहुपद-समय ट्यूरिंग कमी एक एल्गोरिदम है जो समस्या ''B'' के लिए एक सबरूटीन को कॉल की बहुपद संख्या और उन सबरूटीन कॉल के बाहर बहुपद समय का उपयोग करके समस्या ''A'' को हल करती है। पॉलीनोमियल-टाइम ट्यूरिंग अल्पीकरण को 'कुक अल्पीकरण' के नाम से भी जाना जाता है, जिसका नाम [[स्टीफन कुक]] के नाम पर रखा गया है। इस प्रकार की कमी को अभिव्यक्ति <math>A \le_T^P B</math> द्वारा निरूपित किया जा सकता है<ref name="goldreich"/> अनेक-एक अल्पीकरण को ट्यूरिंग अल्पीकरण के प्रतिबंधित प्रकार के रूप में माना जा सकता है जहां समस्या ''B'' के लिए सबरूटीन में की गई कॉल की संख्या पूर्ण रूप से एक है और अल्पीकरण द्वारा लौटाया गया मान वही है जो सबरूटीन द्वारा लौटाया गया है। | ||
== संपूर्णता == | == संपूर्णता == | ||
किसी दिए गए जटिलता वर्ग '''C''' और कमी ≤ के लिए एक पूर्ण समस्या एक समस्या | किसी दिए गए जटिलता वर्ग '''C'<nowiki/>'''''और कमी ≤ के लिए एक पूर्ण समस्या एक समस्या P'' ' है जो '''C''' से संबंधित है, जैसे कि '''C''' में हर समस्या ''A'' में कमी ''A'' ≤ ''P'' है . उदाहरण के लिए एक समस्या NP-पूर्ण | NP-पूर्ण है यदि यह NP (जटिलता) से संबंधित है और NP में सभी समस्याओं में बहुपद-समय की कई-एक कमी है। एक समस्या जो NP से संबंधित है एक ज्ञात NP-पूर्ण समस्या से एक एकल बहुपद-बार कई-एक कमी को खोजने के द्वारा NP-पूर्ण सिद्ध हो सकती है।<ref>{{citation|title=Computers and Intractability: A Guide to the Theory of NP-Completeness|first1=Michael R.|last1=Garey|author1-link=Michael Garey|first2=D. S.|last2=Johnson|author2-link=David S. Johnson|publisher=W. H. Freeman|year=1979}}.</ref> पी स्पेस-पूर्ण | ||
[[औपचारिक भाषा]] और एक्सपटाइम-पूर्ण भाषाओं सहित अन्य जटिलता वर्गों के लिए पूर्ण समस्याओं को परिभाषित करने के लिए बहुपद-समय कई-एक अल्पीकरण का उपयोग किया गया है।<ref>{{citation|contribution=Complexity theory|pages=241–267|first=A. V.|last=Aho|authorlink=Alfred Aho|title=Computer Science: The Hardware, Software and Heart of It|doi=10.1007/978-1-4614-1168-0_12|year=2011|editor1-first=E. K.|editor1-last=Blum|editor2-first=A. V.|editor2-last=Aho|isbn=978-1-4614-1167-3|doi-access=free}}. See in particular p. 255.</ref> | |||
'''P''' (जटिलता) में हर निर्णय समस्या (बहुपद-समय की निर्णय समस्याओं का वर्ग) को हर दूसरी गैर-तुच्छ निर्णय समस्या में कम किया जा सकता है (जहां गैर-तुच्छ का अर्थ है कि हर इनपुट का एक ही आउटपुट नहीं है) एक बहुपद-समय कई-एक कमी से . समस्या ' A को 'B' में बदलने के लिए, बहुपद समय में 'A ' को हल करें, और फिर अलग-अलग उत्तरों के साथ समस्या 'B' के दो उदाहरणों में से एक को चुनने के लिए समाधान का उपयोग करें। इसलिए, '''P''' के अंदर | '''P''' (जटिलता) में हर निर्णय समस्या (बहुपद-समय की निर्णय समस्याओं का वर्ग) को हर दूसरी गैर-तुच्छ निर्णय समस्या में कम किया जा सकता है (जहां गैर-तुच्छ का अर्थ है कि हर इनपुट का एक ही आउटपुट नहीं है) एक बहुपद-समय कई-एक कमी से . समस्या ' A को 'B' में बदलने के लिए, बहुपद समय में 'A ' को हल करें, और फिर अलग-अलग उत्तरों के साथ समस्या 'B' के दो उदाहरणों में से एक को चुनने के लिए समाधान का उपयोग करें। इसलिए, '''P''' के अंदर जटिलता वर्गों जैसे '''L''', '''NL''', '''NC''', और '''P''' स्वयं के लिए बहुपद-समय में अल्पीकरण का उपयोग पूर्ण भाषाओं को परिभाषित करने के लिए नहीं किया जा सकता है: यदि उनका उपयोग इस तरह से किया जाता है, तो प्रत्येक गैर-तुच्छ P में समस्या पूरी होगी। इसके अतिरिक्त लॉग-स्पेस अल्पीकरण या '''NC''' अल्पीकरण जैसे अशक्त अल्पीकरण का उपयोग इन वर्गों के लिए पूर्ण समस्याओं जैसे '''P'''-पूर्ण समस्याओं के वर्गों को परिभाषित करने के लिए किया जाता है।।<ref>{{citation|last1=Greenlaw|first1=Raymond|first2=James|last2=Hoover|first3=Walter|last3=Ruzzo|year=1995|title=Limits To Parallel computation; P-Completeness Theory|isbn=978-0-19-508591-4}}. In particular, for the argument that every nontrivial problem in P has a polynomial-time many-one reduction to every other nontrivial problem, see p. 48.</ref> | ||
== जटिलता वर्गों को परिभाषित करना == | == जटिलता वर्गों को परिभाषित करना == | ||
जटिलता वर्ग एनपी, पी स्पेस, और एक्सपटाइम की परिभाषाओं में | जटिलता वर्ग एनपी, पी स्पेस, और एक्सपटाइम की परिभाषाओं में अल्पीकरण सम्मिलित नहीं है: इन वर्गों के लिए पूर्ण भाषाओं की परिभाषा में अल्पीकरण केवल उनके अध्ययन में आती है। चूँकि कुछ स्थिति में एक जटिलता वर्ग को अल्पीकरण द्वारा परिभाषित किया जा सकता है। यदि '''C''' कोई निर्णय समस्या है तो कोई जटिलता वर्ग '''C''' को परिभाषित कर सकता है जिसमें ''A'' भाषाएं सम्मिलित हैं जिसके लिए <math>A \le_m^P C</math>. इस स्थिति में '''C''' स्वचालित रूप से ''''C''' ' के लिए पूर्ण हो जाएगा, किंतु ''''C''' ' में अन्य पूर्ण समस्याएं भी हो सकती हैं। | ||
इसका एक उदाहरण वास्तविकता के अस्तित्व सिद्धांत से परिभाषित जटिलता वर्ग <math>\exists \mathbb{R}</math> है एक कम्प्यूटेशनल समस्या जिसे NP-हार्ड और पीएसपीएसीई में जाना जाता है, किंतु '''NP''' पीएसपीएसीई के लिए पूर्ण होने के लिए ज्ञात नहीं है या बहुपद पदानुक्रम में कोई भी भाषा <math>\exists \mathbb{R}</math> समस्याओं का समूह है जिसमें वास्तविकताओं के अस्तित्वपरक सिद्धांत में बहुपद-समय बहु-एक कमी है; इसमें कई अन्य पूर्ण समस्याएँ हैं जैसे कि एक अप्रत्यक्ष ग्राफ़ की सीधीरेखीय क्रॉसिंग संख्या निर्धारित करना<math>\exists \mathbb{R}</math> में प्रत्येक समस्या पी स्पेस से संबंधित संपत्ति को इनहेरिट करती है, और प्रत्येक <math>\exists \mathbb{R}</math>-पूर्ण समस्या NP-हार्ड है। | इसका एक उदाहरण वास्तविकता के अस्तित्व सिद्धांत से परिभाषित जटिलता वर्ग <math>\exists \mathbb{R}</math> है एक कम्प्यूटेशनल समस्या जिसे NP-हार्ड और पीएसपीएसीई में जाना जाता है, किंतु '''NP''' पीएसपीएसीई के लिए पूर्ण होने के लिए ज्ञात नहीं है या बहुपद पदानुक्रम में कोई भी भाषा <math>\exists \mathbb{R}</math> समस्याओं का समूह है जिसमें वास्तविकताओं के अस्तित्वपरक सिद्धांत में बहुपद-समय बहु-एक कमी है; इसमें कई अन्य पूर्ण समस्याएँ हैं जैसे कि एक अप्रत्यक्ष ग्राफ़ की सीधीरेखीय क्रॉसिंग संख्या निर्धारित करना<math>\exists \mathbb{R}</math> में प्रत्येक समस्या पी स्पेस से संबंधित संपत्ति को इनहेरिट करती है, और प्रत्येक <math>\exists \mathbb{R}</math>-पूर्ण समस्या NP-हार्ड है। | ||
इसी तरह जटिलता वर्ग '''GI''' (जटिलता) में ऐसी समस्याएं सम्मिलित | इसी तरह जटिलता वर्ग '''GI''' (जटिलता) में ऐसी समस्याएं सम्मिलित हैं जिन्हें [[ग्राफ समरूपता समस्या]] में कम किया जा सकता है। चूंकि ग्राफ समरूपता NP और सह-'''AM''' (जटिलता) दोनों से संबंधित है इस वर्ग की हर समस्या के लिए भी यही सच है। एक समस्या '''GI'''-पूर्ण है यदि यह इस वर्ग के लिए पूर्ण है ग्राफ समरूपता समस्या स्वयं '''GI'''-पूर्ण है जैसा कि कई अन्य संबंधित समस्याएं हैं।<ref>{{citation | ||
| first1 = Johannes | last1 = Köbler | | first1 = Johannes | last1 = Köbler | ||
| first2 = Uwe | last2 = Schöning | author2-link = Uwe Schöning | | first2 = Uwe | last2 = Schöning | author2-link = Uwe Schöning | ||
| Line 51: | Line 51: | ||
| isbn = 978-0-8176-3680-7 | | isbn = 978-0-8176-3680-7 | ||
| oclc = 246882287}}.</ref> | | oclc = 246882287}}.</ref> | ||
== यह भी देखें == | |||
== यह भी देखें | |||
* कार्प की 21 एनपी -पूर्ण समस्याएं | * कार्प की 21 एनपी -पूर्ण समस्याएं | ||
| Line 63: | Line 61: | ||
{{reflist}} | {{reflist}} | ||
{{DEFAULTSORT:Polynomial-Time Reduction}} | {{DEFAULTSORT:Polynomial-Time Reduction}} | ||
[[he:רדוקציה פולינומית]] | [[he:רדוקציה פולינומית]] | ||
[[Category:Created On 15/05/2023|Polynomial-Time Reduction]] | |||
[[Category:Lua-based templates|Polynomial-Time Reduction]] | |||
[[Category: Machine Translated Page]] | [[Category:Machine Translated Page|Polynomial-Time Reduction]] | ||
[[Category: | [[Category:Pages with script errors|Polynomial-Time Reduction]] | ||
[[Category:Templates Vigyan Ready|Polynomial-Time Reduction]] | |||
[[Category:Templates that add a tracking category|Polynomial-Time Reduction]] | |||
[[Category:Templates that generate short descriptions|Polynomial-Time Reduction]] | |||
[[Category:Templates using TemplateData|Polynomial-Time Reduction]] | |||
[[Category:कमी (जटिलता)|Polynomial-Time Reduction]] | |||
Latest revision as of 16:43, 12 June 2023
कम्प्यूटेशनल जटिलता सिद्धांत में एक बहुपद-समय में कमी एक समस्या को दूसरे का उपयोग करके हल करने की एक विधि है। एक से पता चलता है कि यदि दूसरी समस्या को हल करने वाला एक काल्पनिक सबरूटीन उपस्थित है तो पहली समस्या को दूसरी समस्या के लिए इनपुट में परिवर्तित या घटाकर (जटिलता) करके और सबरूटीन को एक या अधिक बार कॉल करके हल किया जा सकता है। यदि पहली समस्या को दूसरी समस्या में बदलने के लिए आवश्यक समय और सबरूटीन को जितनी बार कहा जाता है वह बहुपद है तो पहली समस्या बहुपद-समय को दूसरी तक कम करने योग्य है।[1]
एक बहुपद-समय में कमी यह सिद्ध करती है कि पहली समस्या दूसरी समस्या से अधिक कठिन नहीं है क्योंकि जब भी दूसरी समस्या के लिए एक कुशल कलन विधि उपस्थित होता है तो पहली समस्या के लिए भी उपस्थित होता है। विरोधाभास से यदि पहली समस्या के लिए कोई कुशल एल्गोरिदम उपस्थित नहीं है तो दूसरे के लिए भी कोई अस्तित्व नहीं है।[1] जटिलता वर्ग और उन वर्गों के लिए पूर्ण समस्याओं दोनों को परिभाषित करने के लिए बहुपद-समय की अल्पीकरण अधिकांशतः जटिलता सिद्धांत में उपयोग की जाती है।
अल्पीकरण के प्रकार
तीन सबसे सामान्य प्रकार के बहुपद-समय में कमी सबसे कम से कम प्रतिबंधात्मक बहुपद-समय में कई-एक अल्पीकरण सत्य-तालिका में कमी और ट्यूरिंग अल्पीकरण हैं। इनमें से सबसे अधिक बार उपयोग किए जाने वाले कई-एक अल्पीकरण हैं, और कुछ स्थिति में वाक्यांश बहुपद-समय में कमी का अर्थ बहुपद-समय में कई-एक कमी के लिए किया जा सकता है।[2] सबसे सामान्य अल्पीकरण ट्यूरिंग अल्पीकरण हैं और सबसे अधिक प्रतिबंधक कई-एक अल्पीकरण हैं जिनके बीच में जगह घेरने वाली सत्य-तालिका अल्पीकरण होती है।[3]
अनेक-एक अल्पीकरण
समस्या A से समस्या B तक एक बहुपद-समय कई-एक कमी (दोनों जिनमें सामान्यतः निर्णय की समस्या होने की आवश्यकता होती है) एक बहुपद-समय एल्गोरिथ्म है जो इनपुट को समस्या A से समस्या B में इनपुट में बदलने के लिए है जैसे कि रूपांतरित समस्या का आउटपुट मूल समस्या के समान होता है। समस्या A का एक उदाहरण x समस्या B का एक उदाहरण y उत्पन्न करने के लिए इस परिवर्तन को प्रयुक्त करके हल किया जा सकता है समस्या B के लिए एक एल्गोरिथम के इनपुट के रूप में y दे रहा है और इसके आउटपुट को वापस कर रहा है। बहुपद-समय कई-एक अल्पीकरण को रिचर्ड कार्प के नाम पर 'बहुपद परिवर्तन' या 'कार्प अल्पीकरण' के रूप में भी जाना जा सकता है। इस प्रकार की कमी को या द्वारा निरूपित किया जाता है।.[4][1]
सत्य तालिका में कमी
समस्या A से समस्या B (दोनों निर्णय समस्याएं) में एक बहुपद-समय की सत्य-सारणी में कमी एक बहुपद समय एल्गोरिदम है जो इनपुट को समस्या A में इनपुट की एक निश्चित संख्या में समस्या B में बदलने के लिए है, जैसे कि मूल समस्या के लिए आउटपुट B के लिए आउटपुट के एक फलन के रूप में व्यक्त किया जा सकता है। A के लिए आउटपुट में B के लिए आउटपुट मैप करने वाला फलन सभी इनपुट के लिए समान होना चाहिए जिससे इसे सत्य तालिका द्वारा व्यक्त किया जा सकता है । इस प्रकार की कमी को अभिव्यक्ति द्वारा निरूपित किया जा सकता है .[5]
ट्यूरिंग अल्पीकरण
एक समस्या A से एक समस्या B तक एक बहुपद-समय ट्यूरिंग कमी एक एल्गोरिदम है जो समस्या B के लिए एक सबरूटीन को कॉल की बहुपद संख्या और उन सबरूटीन कॉल के बाहर बहुपद समय का उपयोग करके समस्या A को हल करती है। पॉलीनोमियल-टाइम ट्यूरिंग अल्पीकरण को 'कुक अल्पीकरण' के नाम से भी जाना जाता है, जिसका नाम स्टीफन कुक के नाम पर रखा गया है। इस प्रकार की कमी को अभिव्यक्ति द्वारा निरूपित किया जा सकता है[4] अनेक-एक अल्पीकरण को ट्यूरिंग अल्पीकरण के प्रतिबंधित प्रकार के रूप में माना जा सकता है जहां समस्या B के लिए सबरूटीन में की गई कॉल की संख्या पूर्ण रूप से एक है और अल्पीकरण द्वारा लौटाया गया मान वही है जो सबरूटीन द्वारा लौटाया गया है।
संपूर्णता
किसी दिए गए जटिलता वर्ग C'और कमी ≤ के लिए एक पूर्ण समस्या एक समस्या P ' है जो C से संबंधित है, जैसे कि C में हर समस्या A में कमी A ≤ P है . उदाहरण के लिए एक समस्या NP-पूर्ण | NP-पूर्ण है यदि यह NP (जटिलता) से संबंधित है और NP में सभी समस्याओं में बहुपद-समय की कई-एक कमी है। एक समस्या जो NP से संबंधित है एक ज्ञात NP-पूर्ण समस्या से एक एकल बहुपद-बार कई-एक कमी को खोजने के द्वारा NP-पूर्ण सिद्ध हो सकती है।[6] पी स्पेस-पूर्ण
औपचारिक भाषा और एक्सपटाइम-पूर्ण भाषाओं सहित अन्य जटिलता वर्गों के लिए पूर्ण समस्याओं को परिभाषित करने के लिए बहुपद-समय कई-एक अल्पीकरण का उपयोग किया गया है।[7]
P (जटिलता) में हर निर्णय समस्या (बहुपद-समय की निर्णय समस्याओं का वर्ग) को हर दूसरी गैर-तुच्छ निर्णय समस्या में कम किया जा सकता है (जहां गैर-तुच्छ का अर्थ है कि हर इनपुट का एक ही आउटपुट नहीं है) एक बहुपद-समय कई-एक कमी से . समस्या ' A को 'B' में बदलने के लिए, बहुपद समय में 'A ' को हल करें, और फिर अलग-अलग उत्तरों के साथ समस्या 'B' के दो उदाहरणों में से एक को चुनने के लिए समाधान का उपयोग करें। इसलिए, P के अंदर जटिलता वर्गों जैसे L, NL, NC, और P स्वयं के लिए बहुपद-समय में अल्पीकरण का उपयोग पूर्ण भाषाओं को परिभाषित करने के लिए नहीं किया जा सकता है: यदि उनका उपयोग इस तरह से किया जाता है, तो प्रत्येक गैर-तुच्छ P में समस्या पूरी होगी। इसके अतिरिक्त लॉग-स्पेस अल्पीकरण या NC अल्पीकरण जैसे अशक्त अल्पीकरण का उपयोग इन वर्गों के लिए पूर्ण समस्याओं जैसे P-पूर्ण समस्याओं के वर्गों को परिभाषित करने के लिए किया जाता है।।[8]
जटिलता वर्गों को परिभाषित करना
जटिलता वर्ग एनपी, पी स्पेस, और एक्सपटाइम की परिभाषाओं में अल्पीकरण सम्मिलित नहीं है: इन वर्गों के लिए पूर्ण भाषाओं की परिभाषा में अल्पीकरण केवल उनके अध्ययन में आती है। चूँकि कुछ स्थिति में एक जटिलता वर्ग को अल्पीकरण द्वारा परिभाषित किया जा सकता है। यदि C कोई निर्णय समस्या है तो कोई जटिलता वर्ग C को परिभाषित कर सकता है जिसमें A भाषाएं सम्मिलित हैं जिसके लिए . इस स्थिति में C स्वचालित रूप से 'C ' के लिए पूर्ण हो जाएगा, किंतु 'C ' में अन्य पूर्ण समस्याएं भी हो सकती हैं।
इसका एक उदाहरण वास्तविकता के अस्तित्व सिद्धांत से परिभाषित जटिलता वर्ग है एक कम्प्यूटेशनल समस्या जिसे NP-हार्ड और पीएसपीएसीई में जाना जाता है, किंतु NP पीएसपीएसीई के लिए पूर्ण होने के लिए ज्ञात नहीं है या बहुपद पदानुक्रम में कोई भी भाषा समस्याओं का समूह है जिसमें वास्तविकताओं के अस्तित्वपरक सिद्धांत में बहुपद-समय बहु-एक कमी है; इसमें कई अन्य पूर्ण समस्याएँ हैं जैसे कि एक अप्रत्यक्ष ग्राफ़ की सीधीरेखीय क्रॉसिंग संख्या निर्धारित करना में प्रत्येक समस्या पी स्पेस से संबंधित संपत्ति को इनहेरिट करती है, और प्रत्येक -पूर्ण समस्या NP-हार्ड है।
इसी तरह जटिलता वर्ग GI (जटिलता) में ऐसी समस्याएं सम्मिलित हैं जिन्हें ग्राफ समरूपता समस्या में कम किया जा सकता है। चूंकि ग्राफ समरूपता NP और सह-AM (जटिलता) दोनों से संबंधित है इस वर्ग की हर समस्या के लिए भी यही सच है। एक समस्या GI-पूर्ण है यदि यह इस वर्ग के लिए पूर्ण है ग्राफ समरूपता समस्या स्वयं GI-पूर्ण है जैसा कि कई अन्य संबंधित समस्याएं हैं।[9]
यह भी देखें
- कार्प की 21 एनपी -पूर्ण समस्याएं
बाहरी संबंध
संदर्भ
- ↑ 1.0 1.1 1.2 Kleinberg, Jon; Tardos, Éva (2006). Algorithm Design. Pearson Education. pp. 452–453. ISBN 978-0-321-37291-8.
- ↑ Wegener, Ingo (2005), Complexity Theory: Exploring the Limits of Efficient Algorithms, Springer, p. 60, ISBN 9783540274773.
- ↑ Mandal, Debasis; Pavan, A.; Venugopalan, Rajeswari (2014). वर्स्ट-केस कठोरता परिकल्पना के तहत कार्प-लेविन पूर्णता से कुक पूर्णता को अलग करना. 34th International Conference on Foundation of Software Technology and Theoretical Computer Science. ISBN 978-3-939897-77-4.
- ↑ 4.0 4.1 Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective, Cambridge University Press, pp. 59–60, ISBN 9781139472746
- ↑ Buss, S.R.; Hay, L. (1988), "On truth-table reducibility to SAT and the difference hierarchy over NP", Proceedings of Third Annual Structure in Complexity Theory Conference, pp. 224–233, CiteSeerX 10.1.1.5.2387, doi:10.1109/SCT.1988.5282, ISBN 978-0-8186-0866-7.
- ↑ Garey, Michael R.; Johnson, D. S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman.
- ↑ Aho, A. V. (2011), "Complexity theory", in Blum, E. K.; Aho, A. V. (eds.), Computer Science: The Hardware, Software and Heart of It, pp. 241–267, doi:10.1007/978-1-4614-1168-0_12, ISBN 978-1-4614-1167-3. See in particular p. 255.
- ↑ Greenlaw, Raymond; Hoover, James; Ruzzo, Walter (1995), Limits To Parallel computation; P-Completeness Theory, ISBN 978-0-19-508591-4. In particular, for the argument that every nontrivial problem in P has a polynomial-time many-one reduction to every other nontrivial problem, see p. 48.
- ↑ Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1993), The Graph Isomorphism Problem: Its Structural Complexity, Birkhäuser, ISBN 978-0-8176-3680-7, OCLC 246882287.
