बहुपद-समय में कमी: Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|Method for solving one problem using another}} कम्प्यूटेशनल जटिलता सिद्धांत में, एक ...")
 
No edit summary
Line 1: Line 1:
{{Short description|Method for solving one problem using another}}
{{Short description|Method for solving one problem using another}}


[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, एक [[बहुपद]]-समय में कमी एक समस्या को दूसरे का उपयोग करके हल करने की एक विधि है। एक से पता चलता है कि यदि दूसरी समस्या को हल करने वाला एक काल्पनिक [[सबरूटीन]] मौजूद है, तो पहली समस्या को दूसरी समस्या के लिए इनपुट में परिवर्तित या घटाकर (जटिलता) करके और सबरूटीन को एक या अधिक बार कॉल करके हल किया जा सकता है। यदि पहली समस्या को दूसरी समस्या में बदलने के लिए आवश्यक समय, और सबरूटीन को जितनी बार कहा जाता है, वह बहुपद है, तो पहली समस्या बहुपद-समय को दूसरी तक कम करने योग्य है।<ref name = "kleinberg-tardos">{{cite book | last1=Kleinberg | first1=Jon|authorlink1= Jon Kleinberg| last2=Tardos | first2=Éva|authorlink2=Éva Tardos
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में एक [[बहुपद]]-समय में कमी एक समस्या को दूसरे का उपयोग करके हल करने की एक विधि है। एक से पता चलता है कि यदि दूसरी समस्या को हल करने वाला एक काल्पनिक [[सबरूटीन]] उपस्थित है तो पहली समस्या को दूसरी समस्या के लिए इनपुट में परिवर्तित या घटाकर (जटिलता) करके और सबरूटीन को एक या अधिक बार कॉल करके हल किया जा सकता है। यदि पहली समस्या को दूसरी समस्या में बदलने के लिए आवश्यक समय और सबरूटीन को जितनी बार कहा जाता है वह बहुपद है तो पहली समस्या बहुपद-समय को दूसरी तक कम करने योग्य है।<ref name = "kleinberg-tardos">{{cite book | last1=Kleinberg | first1=Jon|authorlink1= Jon Kleinberg| last2=Tardos | first2=Éva|authorlink2=Éva Tardos
|year=2006
|year=2006
|publisher=Pearson Education
|publisher=Pearson Education
Line 9: Line 9:
}}
}}
</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>


== अल्पीकरण के प्रकार ==
तीन सबसे सामान्य प्रकार के बहुपद-समय में कमी सबसे कम से कम प्रतिबंधात्मक बहुपद-समय में कई-एक अल्पीकरण सत्य-तालिका में कमी और ट्यूरिंग अल्पीकरण हैं। इनमें से सबसे अधिक बार उपयोग किए जाने वाले कई-एक  अल्पीकरण हैं, और कुछ स्थिति में वाक्यांश बहुपद-समय में कमी का अर्थ बहुपद-समय में कई-एक कमी के लिए किया जा सकता है।<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 दे रहा है, और इसके आउटपुट को वापस कर रहा है। बहुपद-समय कई-एक कटौती को [[रिचर्ड कार्प]] के नाम पर 'बहुपद परिवर्तन' या 'कार्प कटौती' के रूप में भी जाना जा सकता है। इस प्रकार की कमी को इसके द्वारा निरूपित किया जाता है <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 का एक उदाहरण 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"/>
===सत्य तालिका में कमी ===
===सत्य तालिका में कमी ===
समस्या ए से समस्या बी (दोनों निर्णय समस्याएं) में एक बहुपद-समय की सत्य-सारणी में कमी एक बहुपद समय एल्गोरिदम है जो इनपुट को समस्या ए में इनपुट की एक निश्चित संख्या में समस्या बी में बदलने के लिए है, जैसे कि मूल समस्या के लिए आउटपुट बी के लिए आउटपुट के एक फ़ंक्शन के रूप में व्यक्त किया जा सकता है। ए के लिए आउटपुट में बी के लिए आउटपुट मैप करने वाला फ़ंक्शन सभी इनपुट के लिए समान होना चाहिए, ताकि इसे सत्य तालिका द्वारा व्यक्त किया जा सके। इस प्रकार की कमी को अभिव्यक्ति द्वारा निरूपित किया जा सकता है <math>A \le_{tt}^P B</math>.<ref>{{citation
समस्या ''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 28: Line 28:
  | title = Proceedings of Third Annual Structure in Complexity Theory Conference
  | title = Proceedings of Third Annual Structure in Complexity Theory Conference
  | 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''  को हल करती है। पॉलीनोमियल-टाइम ट्यूरिंग अल्पीकरण को 'कुक अल्पीकरण' के नाम से भी जाना जाता है, जिसका नाम [[स्टीफन कुक]] के नाम पर रखा गया है। इस प्रकार की कमी को अभिव्यक्ति <math>A \le_T^P B</math> द्वारा निरूपित किया जा सकता है<ref name="goldreich"/> अनेक-एक अल्पीकरण को ट्यूरिंग अल्पीकरण के प्रतिबंधित प्रकार के रूप में माना जा सकता है जहां समस्या ''B''  के लिए सबरूटीन में की गई कॉल की संख्या पूर्ण रूप से  एक है और अल्पीकरण द्वारा लौटाया गया मान वही है जो सबरूटीन द्वारा लौटाया गया है।
=== ट्यूरिंग रिडक्शन ===
एक समस्या ए से एक समस्या बी तक एक बहुपद-समय ट्यूरिंग कमी एक एल्गोरिदम है जो समस्या बी के लिए एक सबरूटीन को कॉल की बहुपद संख्या और उन सबरूटीन कॉल के बाहर बहुपद समय का उपयोग करके समस्या ए को हल करती है। पॉलीनोमियल-टाइम ट्यूरिंग रिडक्शन को 'कुक रिडक्शन' के नाम से भी जाना जाता है, जिसका नाम [[स्टीफन कुक]] के नाम पर रखा गया है। इस प्रकार की कमी को अभिव्यक्ति द्वारा निरूपित किया जा सकता है <math>A \le_T^P B</math>.<ref name="goldreich"/>मैनी-वन रिडक्शन को ट्यूरिंग रिडक्शन के प्रतिबंधित वेरिएंट के रूप में माना जा सकता है, जहां समस्या बी के लिए सबरूटीन में की गई कॉल की संख्या बिल्कुल एक है और रिडक्शन द्वारा लौटाया गया मान वही है जो सबरूटीन द्वारा लौटाया गया है।


== संपूर्णता ==
== संपूर्णता ==
किसी दिए गए जटिलता वर्ग सी और कमी ≤ के लिए एक पूर्ण समस्या एक समस्या 'पी' है जो सी से संबंधित है, जैसे कि सी में हर समस्या '' ए '' में कमी '' ए '' ≤ '' पी '' है . उदाहरण के लिए, एक समस्या एनपी-पूर्ण | एनपी-पूर्ण है यदि यह एनपी (जटिलता) से संबंधित है और एनपी में सभी समस्याओं में बहुपद-समय की कई-एक कमी है। एक समस्या जो एनपी से संबंधित है, एक ज्ञात एनपी-पूर्ण समस्या से एक एकल बहुपद-बार कई-एक कमी को खोजने के द्वारा एनपी-पूर्ण साबित हो सकती है।<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> PSPACE-पूर्ण|PSPACE-पूर्ण [[औपचारिक भाषा]] और EXPTIME|EXPTIME-पूर्ण भाषाओं सहित अन्य जटिलता वर्गों के लिए पूर्ण समस्याओं को परिभाषित करने के लिए बहुपद-समय कई-एक कटौती का उपयोग किया गया है।<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.&nbsp;255.</ref>
किसी दिए गए जटिलता वर्ग '''C''' और कमी ≤ के लिए एक पूर्ण समस्या एक समस्या '''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> पी स्पेस-पूर्ण
पी (जटिलता) में हर निर्णय समस्या (बहुपद-समय की निर्णय समस्याओं का वर्ग) को हर दूसरी गैर-तुच्छ निर्णय समस्या में कम किया जा सकता है (जहां गैर-तुच्छ का मतलब है कि हर इनपुट का एक ही आउटपुट नहीं है), एक बहुपद-समय कई-एक कमी से . समस्या 'ए'' को 'बी' में बदलने के लिए, बहुपद समय में 'ए' को हल करें, और फिर अलग-अलग उत्तरों के साथ समस्या 'बी' के दो उदाहरणों में से एक को चुनने के लिए समाधान का उपयोग करें। इसलिए, पी के भीतर जटिलता वर्गों जैसे एल (जटिलता), एनएल (जटिलता), एनसी (जटिलता), और पी स्वयं के लिए, बहुपद-समय में कटौती का उपयोग पूर्ण भाषाओं को परिभाषित करने के लिए नहीं किया जा सकता है: यदि उनका उपयोग इस तरह से किया जाता है, तो प्रत्येक गैर-तुच्छ 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.&nbsp;48.</ref>


'''PSPACE-पूर्ण''' [[औपचारिक भाषा]] और एक्सपटाइम '''EXPTIME'''-पूर्ण भाषाओं सहित अन्य जटिलता वर्गों के लिए पूर्ण समस्याओं को परिभाषित करने के लिए बहुपद-समय कई-एक  अल्पीकरण का उपयोग किया गया है।<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.&nbsp;255.</ref>


'''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.&nbsp;48.</ref>
== जटिलता वर्गों को परिभाषित करना ==
== जटिलता वर्गों को परिभाषित करना ==
जटिलता वर्ग NP, PSPACE, और EXPTIME की परिभाषाओं में कटौती शामिल नहीं है: इन वर्गों के लिए पूर्ण भाषाओं की परिभाषा में कटौती केवल उनके अध्ययन में आती है। हालाँकि, कुछ मामलों में एक जटिलता वर्ग को कटौती द्वारा परिभाषित किया जा सकता है। यदि ''सी'' कोई निर्णय समस्या है, तो कोई जटिलता वर्ग सी को परिभाषित कर सकता है जिसमें ''ए'' भाषाएं शामिल हैं जिसके लिए <math>A \le_m^P C</math>. इस मामले में, सी स्वचालित रूप से 'सी' के लिए पूर्ण हो जाएगा, लेकिन 'सी' में अन्य पूर्ण समस्याएं भी हो सकती हैं।
जटिलता वर्ग एनपी, पी स्पेस, और एक्सपटाइम की परिभाषाओं में अल्पीकरण सम्मिलित  नहीं है: इन वर्गों के लिए पूर्ण भाषाओं की परिभाषा में अल्पीकरण केवल उनके अध्ययन में आती है। चूँकि  कुछ स्थिति में एक जटिलता वर्ग को अल्पीकरण द्वारा परिभाषित किया जा सकता है। यदि '''C''' कोई निर्णय समस्या है तो कोई जटिलता वर्ग '''C''' को परिभाषित कर सकता है जिसमें ''A'' भाषाएं सम्मिलित  हैं जिसके लिए <math>A \le_m^P C</math>. इस स्थिति में '''C''' स्वचालित रूप से '<nowiki/>'''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> वास्तविक के अस्तित्व संबंधी सिद्धांत से परिभाषित, एक कम्प्यूटेशनल समस्या जिसे एनपी-हार्ड | एनपी-हार्ड और [[पीएसपीएसीई]] में जाना जाता है, लेकिन एनपी, पीएसपीएसीई, या [[बहुपद पदानुक्रम]] में किसी भी भाषा के लिए पूर्ण होने के लिए नहीं जाना जाता है। <math>\exists \mathbb{R}</math> वास्तविकताओं के अस्तित्वगत सिद्धांत के लिए एक बहुपद-समय कई-एक कमी वाली समस्याओं का समूह है; इसमें कई अन्य पूर्ण समस्याएं हैं जैसे एक [[अप्रत्यक्ष ग्राफ]] के क्रॉसिंग नंबर (ग्राफ सिद्धांत) का निर्धारण करना। में प्रत्येक समस्या <math>\exists \mathbb{R}</math> PSPACE, और प्रत्येक से संबंधित संपत्ति को इनहेरिट करता है <math>\exists \mathbb{R}</math>-पूरी समस्या एनपी-हार्ड है।<ref>{{citation|first=Marcus|last=Schaefer|contribution=Complexity of some geometric and topological problems|contribution-url=http://ovid.cs.depaul.edu/documents/convex.pdf|title=Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, September 2009, Revised Papers|series=Lecture Notes in Computer Science|publisher=Springer-Verlag|volume=5849|pages=334–344|doi=10.1007/978-3-642-11805-0_32|year=2010|title-link=International Symposium on Graph Drawing|isbn=978-3-642-11804-3|doi-access=free}}.</ref>
इसी तरह जटिलता वर्ग '''GI''' (जटिलता) में ऐसी समस्याएं सम्मिलित  हैं जिन्हें [[ग्राफ समरूपता समस्या]] में कम किया जा सकता है। चूंकि ग्राफ समरूपता NP और सह-'''AM''' (जटिलता) दोनों से संबंधित है इस वर्ग की हर समस्या के लिए भी यही सच है। एक समस्या '''GI'''-पूर्ण है यदि यह इस वर्ग के लिए पूर्ण है ग्राफ समरूपता समस्या स्वयं '''GI'''-पूर्ण है जैसा कि कई अन्य संबंधित समस्याएं हैं।<ref>{{citation
इसी तरह, जटिलता वर्ग जीआई (जटिलता) में ऐसी समस्याएं शामिल हैं जिन्हें [[ग्राफ समरूपता समस्या]] में कम किया जा सकता है। चूंकि ग्राफ समरूपता एनपी और सह-एएम (जटिलता) दोनों से संबंधित है, इस वर्ग की हर समस्या के लिए भी यही सच है। एक समस्या जीआई-पूर्ण है यदि यह इस वर्ग के लिए पूर्ण है; ग्राफ समरूपता समस्या स्वयं जीआई-पूर्ण है, जैसा कि कई अन्य संबंधित समस्याएं हैं।<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 52: Line 52:
  | oclc = 246882287}}.</ref>
  | oclc = 246882287}}.</ref>


 
'''एसीई के लिए पूर्ण होने के लिए ज्ञात नहीं है या बहुपद पदानुक्रम में कोई भी भाषा <math>\exists \mathbb{R}</math> समस्याओं का समूह है जिसमें वास्तविकताओं के अस्तित्वपरक सिद्धांत में बहुपद-समय बहु-एक कमी है; इसमें'''
== यह भी देखें ==
== यह भी देखें                                       ==
* कार्प की 21 एनपी-पूर्ण समस्याएं
* कार्प की 21 एनपी -पूर्ण समस्याएं


== बाहरी संबंध ==
== बाहरी संबंध ==

Revision as of 11:07, 25 May 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] पी स्पेस-पूर्ण

PSPACE-पूर्ण औपचारिक भाषा और एक्सपटाइम EXPTIME-पूर्ण भाषाओं सहित अन्य जटिलता वर्गों के लिए पूर्ण समस्याओं को परिभाषित करने के लिए बहुपद-समय कई-एक अल्पीकरण का उपयोग किया गया है।[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. ↑ 1.0 1.1 1.2 Kleinberg, Jon; Tardos, Éva (2006). Algorithm Design. Pearson Education. pp. 452–453. ISBN 978-0-321-37291-8.
  2. ↑ Wegener, Ingo (2005), Complexity Theory: Exploring the Limits of Efficient Algorithms, Springer, p. 60, ISBN 9783540274773.
  3. ↑ 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. ↑ 4.0 4.1 Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective, Cambridge University Press, pp. 59–60, ISBN 9781139472746
  5. ↑ 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.
  6. ↑ Garey, Michael R.; Johnson, D. S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman.
  7. ↑ 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.
  8. ↑ 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.
  9. ↑ 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.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=बहुपद-समय_में_कमी&oldid=181492’