अनेक न्यूनीकरण: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Type of Turing reduction}} | {{Short description|Type of Turing reduction}} | ||
कम्प्यूटेबिलिटी सिद्धांत और कम्प्यूटेशनल [[संगणना सिद्धांत]] में, | कम्प्यूटेबिलिटी सिद्धांत और कम्प्यूटेशनल [[संगणना सिद्धांत]] में, अधिक-एक कमी (जिसे मैपिंग कमी <ref name="Abrahamson2016">{{cite web|url=http://www.cs.ecu.edu/karl/6420/spr16/Notes/Reduction/mapping.html|title=मानचित्रण कटौती|work=CSCI 6420 – Computability and Complexity|date=Spring 2016|first=Karl R.|last=Abrahamson|publisher=East Carolina University|accessdate=2021-11-12}}</ref> भी कहा जाता है) एक कमी है जो एक [[निर्णय समस्या]] के उदाहरणों को परिवर्तित करती है (एक उदाहरण <math>L_1</math> में हो) एक अन्य निर्णय समस्या (चाहे एक उदाहरण <math>L_2</math>) में एक प्रभावी फलन का उपयोग कर रहा है। घटाया गया उदाहरण भाषा <math>L_2</math> में है यदि और केवल यदि प्रारंभिक उदाहरण इसकी भाषा <math>L_1</math> में है। इस प्रकार यदि हम यह तय कर सकते हैं कि <math>L_2</math> उदाहरण <math>L_2</math> भाषा में हैं या नहीं, तो हम कमी और समाधान प्रयुक्त करके यह तय कर सकते हैं कि <math>L_1</math> उदाहरण इसकी भाषा में हैं या नहीं है | ||
<math>L_2</math>. इस प्रकार, | <math>L_2</math>. इस प्रकार, कमी का उपयोग दो समस्याओं की सापेक्ष कम्प्यूटेशनल कठिनाई को मापने के लिए किया जा सकता है। ऐसा कहा जाता है कि <math>L_1</math> कम होकर <math>L_2</math> हो जाता है, यदि समान आदमी के शब्दों में <math>L_2</math> को हल करना <math>L_1</math> की तुलना में कठिन है। कहने का तात्पर्य यह है कि, <math>L_2</math> को हल करने वाले किसी भी एल्गोरिदम का उपयोग (अन्यथा अपेक्षाकृत सरल) प्रोग्राम के भाग के रूप में भी किया जा सकता है जो <math>L_1</math> को हल करता है | ||
अधिक-एक | अधिक-एक कमी एक विशेष स्थिति है और ट्यूरिंग कमी का सशक्त रूप है।<ref name="Abrahamson2016" /> अधिक-एक कमी के साथ, दैवज्ञ (अर्थात, b के लिए हमारा समाधान) को अंत में केवल एक बार प्रयुक्त किया जा सकता है, और उत्तर को संशोधित नहीं किया जा सकता है। इसका कारण यह है कि यदि हम यह दिखाना चाहते हैं कि समस्या A को समस्या B में घटाया जा सकता है, तो हम B के लिए अपने समाधान का उपयोग A के समाधान में केवल एक बार कर सकते हैं, ट्यूरिंग कमी के विपरीत होते है, जहां हम B के लिए अपने समाधान का उपयोग जितनी बार कर सकते हैं a को हल करते समय आवश्यक है। | ||
इसका कारण यह है कि | इसका कारण यह है कि अधिक-एक कमी एक समस्या के उदाहरणों को दूसरी समस्या के उदाहरणों में मैप करती है, जबकि ट्यूरिंग कमी एक समस्या के समाधान की गणना करती है, यह मानते हुए कि दूसरी समस्या को हल करना सरल है। समस्याओं को अलग-अलग जटिलता वर्गों में अलग करने में अधिक-एक कमी अधिक प्रभावी है। चूँकि, अधिक-एक कटौतियों पर बढ़े हुए प्रतिबंधों से उन्हें खोजना अधिक कठिन हो गया है। | ||
अधिक-एक कमी का उपयोग पहली बार [[एमिल पोस्ट]] द्वारा 1944 में प्रकाशित एक पेपर में किया गया था।<ref>E. L. Post, "[https://web.archive.org/web/20180811064242/https://pdfs.semanticscholar.org/ed71/ebe0eee4f88f095247c8b62ba1d3b217a68d.pdf Recursively enumerable sets of positive integers and their decision problems]", [[Bulletin of the American Mathematical Society]] '''50''' (1944) 284–316</ref> इसके पश्चात् [[नॉर्मन शापिरो]] ने 1956 में स्ट्रांग रिड्यूसिबिलिटी नाम से इसी अवधारणा का उपयोग किया था।<ref>Norman Shapiro, "[https://web.archive.org/web/20180811065234/https://pdfs.semanticscholar.org/742b/cb582c02c9658888b8b4fb6191737a5c790c.pdf Degrees of Computability]", [[Transactions of the American Mathematical Society]] '''82''', (1956) 281–299</ref> | |||
| Line 15: | Line 15: | ||
=== औपचारिक भाषाएँ === | === औपचारिक भाषाएँ === | ||
मान लीजिए कि <math>A</math> और <math>B</math> क्रमशः <math>\Sigma</math> और <math>\Gamma</math> [[वर्णमाला (कंप्यूटर विज्ञान)]] पर औपचारिक भाषाएँ हैं। <math>A</math> को <math>B</math> तक अनेक-एक कमी एक [[कुल गणना योग्य कार्य|कुल गणना योग्य फलन]] है जिसमें यह प्रोपर्टी है कि प्रत्येक शब्द <math>w</math> <math>A</math> में है यदि और केवल यदि <math>f(w)</math> <math>B</math> में है | मान लीजिए कि <math>A</math> और <math>B</math> क्रमशः <math>\Sigma</math> और <math>\Gamma</math> [[वर्णमाला (कंप्यूटर विज्ञान)]] पर औपचारिक भाषाएँ हैं। <math>A</math> को <math>B</math> तक अनेक-एक कमी एक [[कुल गणना योग्य कार्य|कुल गणना योग्य फलन]] है जिसमें यह प्रोपर्टी है कि प्रत्येक शब्द <math>w</math> <math>A</math> में है यदि और केवल यदि <math>f(w)</math> <math>B</math> में है | ||
| Line 26: | Line 24: | ||
=== प्राकृत संख्याओं का उपसमुच्चय === | === प्राकृत संख्याओं का उपसमुच्चय === | ||
दो समुच्चय दिए गए <math>A,B \subseteq \mathbb{N}</math> हम कहते हैं <math>A</math> | दो समुच्चय दिए गए <math>A,B \subseteq \mathbb{N}</math> हम कहते हैं <math>A</math> और <math>B</math> कम करने योग्य है | ||
:<math>A \leq_{\mathrm{m}} B</math> | :<math>A \leq_{\mathrm{m}} B</math> | ||
यदि कुल गणना योग्य फलन <math>f</math> उपस्थित है इस प्रकार साथ <math>x\in A</math> आईएफएफ <math>f(x)\in B</math>. है यदि इसके अतिरिक्त <math>f</math> [[आपत्ति]] है, हम कहते हैं <math>A</math> के लिए पुनरावर्ती <math>B</math> रूप से समरूपी है <ref name="Odifreddi89">P. Odifreddi, ''Classical Recursion Theory: The theory of functions and sets of natural numbers'' (p.320). Studies in Logic and the Foundations of Mathematics, vol. 125 (1989), Elsevier 0-444-87295-7.</ref> | यदि कुल गणना योग्य फलन <math>f</math> उपस्थित है इस प्रकार साथ <math>x\in A</math> आईएफएफ <math>f(x)\in B</math>. है यदि इसके अतिरिक्त <math>f</math> [[आपत्ति|विशेषण]] है, हम कहते हैं <math>A</math> के लिए पुनरावर्ती <math>B</math> रूप से समरूपी है <ref name="Odifreddi89">P. Odifreddi, ''Classical Recursion Theory: The theory of functions and sets of natural numbers'' (p.320). Studies in Logic and the Foundations of Mathematics, vol. 125 (1989), Elsevier 0-444-87295-7.</ref> | ||
:<math>A\equiv B</math> | :<math>A\equiv B</math> | ||
| Line 34: | Line 32: | ||
=== अधिक-एक तुल्यता === | === अधिक-एक तुल्यता === | ||
यदि <math>A \leq_{\mathrm{m}} B \, \mathrm{and} \, B \leq_{\mathrm{m}} A</math> हम कहते हैं <math>A</math> अधिक-एक समतुल्य या m-समतुल्य <math>B</math> है | यदि <math>A \leq_{\mathrm{m}} B \, \mathrm{and} \, B \leq_{\mathrm{m}} A</math> हम कहते हैं इस प्रकार <math>A</math> अधिक-एक समतुल्य या m-समतुल्य <math>B</math> है | ||
:<math>A \equiv_{\mathrm{m}} B.</math> | :<math>A \equiv_{\mathrm{m}} B.</math> | ||
| Line 40: | Line 38: | ||
=== अधिक-एक पूर्णता (एम-पूर्णता) === | === अधिक-एक पूर्णता (एम-पूर्णता) === | ||
एक समुच्चय <math>B</math> यदि इसे अधिक-एक पूर्ण या केवल 'एम-पूर्ण' कहा जाता है <math>B</math> पुनरावर्ती रूप से गणना योग्य है और प्रत्येक पुनरावर्ती रूप से गणना योग्य समुच्चय है <math>A</math> एम-रेड्यूसिबल <math>B</math> है . | एक समुच्चय <math>B</math> यदि इसे अधिक-एक पूर्ण या केवल 'एम-पूर्ण' कहा जाता है इस प्रकार <math>B</math> पुनरावर्ती रूप से गणना योग्य है और प्रत्येक पुनरावर्ती रूप से गणना योग्य समुच्चय है और <math>A</math> एम-रेड्यूसिबल <math>B</math> है . | ||
==डिग्री == | ==डिग्री == | ||
<math>\equiv_m</math> एक तुल्यता संबंध है, इसके तुल्यता वर्गों को एम-डिग्री कहा जाता है और एक पोसेट बनता है <math>\mathcal D_m</math> द्वारा प्रेरित आदेश के साथ <math>\leq_m</math> | <math>\equiv_m</math> एक तुल्यता संबंध है, इसके तुल्यता वर्गों को एम-डिग्री कहा जाता है और एक पोसेट बनता है इस प्रकार <math>\mathcal D_m</math> द्वारा प्रेरित आदेश के साथ <math>\leq_m</math> का उप्योगुप्योग किया जाता है <ref name="Odifreddi89" /><sup>पृ.257</sup> | ||
m-डिग्री के कुछ गुण, जिनमें से कुछ [[ट्यूरिंग डिग्री]] के अनुरूप गुणों से भिन्न हैं:<ref name="Odifreddi89" /><sup>पृ.555--581</sup> | |||
* एम-डिग्री पर एक अच्छी तरह से परिभाषित जंप | * एम-डिग्री पर एक अच्छी तरह से परिभाषित जंप संचालक है। | ||
* जंप 0 के साथ एकमात्र एम | * जंप 0 के साथ एकमात्र एम<sub>m</sub>-डिग्री' 0<sub>m</sub> है. | ||
* एम-डिग्री | * एम-डिग्री <math>\mathbf a>_m\boldsymbol 0_m'</math> हैं जहां अस्तित्व ही नहीं <math>\mathbf b</math> है जहाँ <math>\mathbf b'=\mathbf a</math>. | ||
* कम से कम तत्व के साथ प्रत्येक गणनीय रैखिक क्रम | * कम से कम तत्व के साथ प्रत्येक गणनीय रैखिक क्रम <math>\mathcal D_m</math> में एम्बेड होता है . | ||
* | * <math>\mathcal D_m</math> का प्रथम क्रम सिद्धांत दूसरे क्रम के अंकगणित के सिद्धांत के लिए समरूपी है। | ||
<math>\mathcal D_m</math> का एक लक्षण वर्णन है जैसा कि अद्वितीय पोसेट अपने आइडियल (समुच्चय सिद्धांत) के अधिक स्पष्ट गुणों को संतुष्ट करता है, एक समान लक्षण वर्णन ट्यूरिंग डिग्री से दूर हो गया है।<ref name="Odifreddi89" /> | |||
<math>\equiv_1</math> एक समतुल्य संबंध है, और इसके समतुल्य वर्ग (जिन्हें 1-डिग्री कहा जाता है) एक स्थिति | <math>\equiv_1</math> एक समतुल्य संबंध है, और इसके समतुल्य वर्ग (जिन्हें 1-डिग्री कहा जाता है) एक स्थिति <math>\leq_1</math> बनाते हैं माईहिल समरूपता प्रमेय|मायहिल समरूपता प्रमेय को सभी समुच्चयो के लिए कहा जा सकता है प्राकृतिक संख्याओं <math>A,B</math> का उपयोग किया जाता है , जो ये <math>A\equiv B\iff A\equiv_1 B</math> दर्शाता है <math>\equiv</math> और <math>\equiv_1</math> समान तुल्यता वर्ग हैं।<ref name="Odifreddi89" /> | ||
== संसाधन सीमाओं के साथ | == संसाधन सीमाओं के साथ अधिक-एक कमी == | ||
अधिक-एक कमी अधिकांशतः संसाधन प्रतिबंधों के अधीन होती हैं, उदाहरण के लिए कि कमी फलन बहुपद समय, <math>AC_0</math> या <math>NC_0</math> परिपथ, या पॉलीलॉगरिदमिक अनुमान लघुगणकीय समिष्ट में गणना योग्य है जहां प्रत्येक बाद की कमी की धारणा पहले की तुलना में अशक्त है; विवरण के लिए [[बहुपद-समय में कमी]] और [[लॉग-स्पेस में कमी]] देखें। | |||
निर्णय संबंधी समस्याओं को देखते हुए <math>A</math> और <math>B</math> और एक [[कलन विधि]] एन जो उदाहरणों | निर्णय संबंधी समस्याओं को देखते हुए <math>A</math> और <math>B</math> और एक [[कलन विधि]] एन जो उदाहरणों <math>B</math> को हल करता है , हम अधिक-एक कमी <math>A</math> को <math>B</math> का उपयोग कर सकते हैं उदाहरणों को हल करने के लिए <math>A</math> का उपयोग करते है: | ||
* | * N के लिए आवश्यक समय और कमी के लिए आवश्यक समय है | ||
* N के लिए आवश्यक अधिकतम | * N के लिए आवश्यक अधिकतम समिष्ट और कमी के लिए आवश्यक समिष्ट है | ||
हम कहते हैं कि भाषाओं का एक वर्ग ' | हम कहते हैं कि भाषाओं का एक वर्ग 'c ' (या प्राकृतिक संख्याओं के घात समुच्चय का एक उपसमूह) अधिक-एक न्यूनता के अनुसार बंद कर दिया जाता है यदि 'c' की किसी भाषा से 'c' के बाहर की भाषा में कोई कमी नहीं होती है। यदि किसी वर्ग को अधिक-एक न्यूनता के अंतर्गत बंद किया जाता है, जिससे अधिक-एक कमी का उपयोग यह दिखाने के लिए किया जा सकता है कि एक समस्या 'c' में एक समस्या को कम करके 'c' में है। अधिक-एक कमी मूल्यवान हैं क्योंकि अधिकांश अच्छी तरह से अध्ययन की गई जटिलता कक्षाएं कुछ प्रकार के अधिक-एक रिड्यूसिबिलिटी के अनुसार बंद होती हैं, जिनमें [[पी (जटिलता)|p (जटिलता)]], [[एनपी (जटिलता)|np (जटिलता)]], L [[एल (जटिलता)|(जटिलता)]], [[एनएल (जटिलता)|NL (जटिलता)]], [[सह-एनपी]], पीएसपीएसीई सम्मिलित हैं। , [[EXP|ऍक्स्प]], और अधिक अन्य उदाहरण के लिए यह ज्ञात है कि सूचीबद्ध पहले चार बहुभुज समय अनुमानों की बहुत अशक्त कमी धारणा तक बंद हैं। चूँकि, ये कक्षाएं सही विधि से अधिक-एक कमी के अनुसार बंद नहीं की गई हैं। | ||
== | == अधिक-एक कमी बढ़ाई गई == | ||
कोई अधिक-एक कमी के सामान्यीकृत | कोई अधिक-एक कमी के सामान्यीकृत स्थितियों के बारे में भी पूछ सकता है। ऐसा ही एक उदाहरण ई-रिडक्शन है, जहां हम विचार करते हैं <math>f:A\to B</math> जो पुनरावर्ती तक सीमित होने के अतिरिक्त पुनरावर्ती <math>f</math> रूप से गणना योग्य हैं . परिणामी रिड्यूसिबिलिटी संबंध <math>\leq_e</math> को दर्शाया गया है , और इसके पोसेट का अध्ययन ट्यूरिंग डिग्री के समान ही किया गया है। उदाहरण के लिए, एक जंप <math>\boldsymbol 0^'_e</math> समुच्चय है ई-डिग्री के लिए ई-डिग्री ट्यूरिंग डिग्री के पोसेट से भिन्न कुछ गुणों को स्वीकार करती है, उदाहरण के लिए हीरे के ग्राफ को नीचे दी गई डिग्री में एम्बेड करता है .<ref>S. Ahmad, [https://www.jstor.org/stable/2274914 Embedding the Diamond in the <math>\Sigma_2</math> Enumeration Degrees] (1991). Journal of Symbolic Logic, vol.56.</ref> | ||
== गुण == | == गुण == | ||
* | * अधिक-एक रिड्यूसिबिलिटी और 1-रिड्यूसिबिलिटी के [[संबंध (गणित)]] [[सकर्मक संबंध]] और रिफ्लेक्सिव संबंध हैं और इस प्रकार प्राकृतिक संख्याओं के [[ सत्ता स्थापित | पॉवरसेट]] पर एक [[पूर्व आदेश|प्रीऑर्डर]] प्रेरित करते हैं। | ||
* <math>A \leq_{\mathrm{m}} B</math> [[अगर और केवल अगर|यदि और केवल यदि]] <math>\mathbb{N} \setminus A \leq_{\mathrm{m}} \mathbb{N} \setminus B.</math> | * <math>A \leq_{\mathrm{m}} B</math> [[अगर और केवल अगर|यदि और केवल यदि]] <math>\mathbb{N} \setminus A \leq_{\mathrm{m}} \mathbb{N} \setminus B.</math> है | ||
* एक समुच्चय [[रुकने की समस्या]] के लिए अधिक-एक को कम करने योग्य है यदि और केवल यदि यह [[पुनरावर्ती रूप से गणना योग्य]] है। यह कहता है कि अधिक-एक न्यूनता के संबंध में, रुकने की समस्या सभी पुनरावर्ती रूप से गणना योग्य समस्याओं में सबसे जटिल है। इस प्रकार रुकने की समस्या पुनः है। | * एक समुच्चय [[रुकने की समस्या]] के लिए अधिक-एक को कम करने योग्य है यदि और केवल यदि यह [[पुनरावर्ती रूप से गणना योग्य]] है। यह कहता है कि अधिक-एक न्यूनता के संबंध में, रुकने की समस्या सभी पुनरावर्ती रूप से गणना योग्य समस्याओं में सबसे जटिल है। इस प्रकार रुकने की समस्या पुनः है। ध्यान दें कि यह एकमात्र आर.ई. नहीं है। | ||
* एक व्यक्तिगत ट्यूरिंग मशीन | * एक व्यक्तिगत ट्यूरिंग मशीन T (अर्थात, इनपुट का समुच्चय जिसके लिए T अंततः रुकती है) के लिए विशेष रुकने की समस्या अधिक-एक पूर्ण है यदि T एक सार्वभौमिक ट्यूरिंग मशीन है। एमिल पोस्ट ने दिखाया कि पुनरावर्ती रूप से असंख्य समुच्चय उपस्थित हैं जो न तो निर्णायकता (तर्क) और न ही एम-पूर्ण हैं, और इसलिए गैर-सार्वभौमिक ट्यूरिंग मशीनें उपस्थित हैं जिनकी व्यक्तिगत रुकने की समस्याएं फिर भी अनिर्णीत हैं। | ||
== कार्प | == कार्प में कमी == | ||
एक बहुपद-समय में कमी|बहुपद-समय में समस्या | एक बहुपद-समय में कमी|बहुपद-समय में समस्या 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">{{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 87: | Line 85: | ||
== संदर्भ == | == संदर्भ == | ||
{{reflist}} | {{reflist}} | ||
[[Category: कमी (जटिलता)]] | [[Category: कमी (जटिलता)]] | ||
Revision as of 14:03, 15 July 2023
कम्प्यूटेबिलिटी सिद्धांत और कम्प्यूटेशनल संगणना सिद्धांत में, अधिक-एक कमी (जिसे मैपिंग कमी [1] भी कहा जाता है) एक कमी है जो एक निर्णय समस्या के उदाहरणों को परिवर्तित करती है (एक उदाहरण में हो) एक अन्य निर्णय समस्या (चाहे एक उदाहरण ) में एक प्रभावी फलन का उपयोग कर रहा है। घटाया गया उदाहरण भाषा में है यदि और केवल यदि प्रारंभिक उदाहरण इसकी भाषा में है। इस प्रकार यदि हम यह तय कर सकते हैं कि उदाहरण भाषा में हैं या नहीं, तो हम कमी और समाधान प्रयुक्त करके यह तय कर सकते हैं कि उदाहरण इसकी भाषा में हैं या नहीं है
. इस प्रकार, कमी का उपयोग दो समस्याओं की सापेक्ष कम्प्यूटेशनल कठिनाई को मापने के लिए किया जा सकता है। ऐसा कहा जाता है कि कम होकर हो जाता है, यदि समान आदमी के शब्दों में को हल करना की तुलना में कठिन है। कहने का तात्पर्य यह है कि, को हल करने वाले किसी भी एल्गोरिदम का उपयोग (अन्यथा अपेक्षाकृत सरल) प्रोग्राम के भाग के रूप में भी किया जा सकता है जो को हल करता है
अधिक-एक कमी एक विशेष स्थिति है और ट्यूरिंग कमी का सशक्त रूप है।[1] अधिक-एक कमी के साथ, दैवज्ञ (अर्थात, b के लिए हमारा समाधान) को अंत में केवल एक बार प्रयुक्त किया जा सकता है, और उत्तर को संशोधित नहीं किया जा सकता है। इसका कारण यह है कि यदि हम यह दिखाना चाहते हैं कि समस्या A को समस्या B में घटाया जा सकता है, तो हम B के लिए अपने समाधान का उपयोग A के समाधान में केवल एक बार कर सकते हैं, ट्यूरिंग कमी के विपरीत होते है, जहां हम B के लिए अपने समाधान का उपयोग जितनी बार कर सकते हैं a को हल करते समय आवश्यक है।
इसका कारण यह है कि अधिक-एक कमी एक समस्या के उदाहरणों को दूसरी समस्या के उदाहरणों में मैप करती है, जबकि ट्यूरिंग कमी एक समस्या के समाधान की गणना करती है, यह मानते हुए कि दूसरी समस्या को हल करना सरल है। समस्याओं को अलग-अलग जटिलता वर्गों में अलग करने में अधिक-एक कमी अधिक प्रभावी है। चूँकि, अधिक-एक कटौतियों पर बढ़े हुए प्रतिबंधों से उन्हें खोजना अधिक कठिन हो गया है।
अधिक-एक कमी का उपयोग पहली बार एमिल पोस्ट द्वारा 1944 में प्रकाशित एक पेपर में किया गया था।[2] इसके पश्चात् नॉर्मन शापिरो ने 1956 में स्ट्रांग रिड्यूसिबिलिटी नाम से इसी अवधारणा का उपयोग किया था।[3]
परिभाषाएँ
औपचारिक भाषाएँ
मान लीजिए कि और क्रमशः और वर्णमाला (कंप्यूटर विज्ञान) पर औपचारिक भाषाएँ हैं। को तक अनेक-एक कमी एक कुल गणना योग्य फलन है जिसमें यह प्रोपर्टी है कि प्रत्येक शब्द में है यदि और केवल यदि में है
यदि ऐसा कोई फलन अस्तित्व में है, हम ऐसा कहते हैं अधिक-एक कम करने योग्य या एम-कम करने योग्य है
प्राकृत संख्याओं का उपसमुच्चय
दो समुच्चय दिए गए हम कहते हैं और कम करने योग्य है
यदि कुल गणना योग्य फलन उपस्थित है इस प्रकार साथ आईएफएफ . है यदि इसके अतिरिक्त विशेषण है, हम कहते हैं के लिए पुनरावर्ती रूप से समरूपी है [4]
अधिक-एक तुल्यता
यदि हम कहते हैं इस प्रकार अधिक-एक समतुल्य या m-समतुल्य है
अधिक-एक पूर्णता (एम-पूर्णता)
एक समुच्चय यदि इसे अधिक-एक पूर्ण या केवल 'एम-पूर्ण' कहा जाता है इस प्रकार पुनरावर्ती रूप से गणना योग्य है और प्रत्येक पुनरावर्ती रूप से गणना योग्य समुच्चय है और एम-रेड्यूसिबल है .
डिग्री
एक तुल्यता संबंध है, इसके तुल्यता वर्गों को एम-डिग्री कहा जाता है और एक पोसेट बनता है इस प्रकार द्वारा प्रेरित आदेश के साथ का उप्योगुप्योग किया जाता है [4]पृ.257
m-डिग्री के कुछ गुण, जिनमें से कुछ ट्यूरिंग डिग्री के अनुरूप गुणों से भिन्न हैं:[4]पृ.555--581
- एम-डिग्री पर एक अच्छी तरह से परिभाषित जंप संचालक है।
- जंप 0 के साथ एकमात्र एमm-डिग्री' 0m है.
- एम-डिग्री हैं जहां अस्तित्व ही नहीं है जहाँ .
- कम से कम तत्व के साथ प्रत्येक गणनीय रैखिक क्रम में एम्बेड होता है .
- का प्रथम क्रम सिद्धांत दूसरे क्रम के अंकगणित के सिद्धांत के लिए समरूपी है।
का एक लक्षण वर्णन है जैसा कि अद्वितीय पोसेट अपने आइडियल (समुच्चय सिद्धांत) के अधिक स्पष्ट गुणों को संतुष्ट करता है, एक समान लक्षण वर्णन ट्यूरिंग डिग्री से दूर हो गया है।[4]
एक समतुल्य संबंध है, और इसके समतुल्य वर्ग (जिन्हें 1-डिग्री कहा जाता है) एक स्थिति बनाते हैं माईहिल समरूपता प्रमेय|मायहिल समरूपता प्रमेय को सभी समुच्चयो के लिए कहा जा सकता है प्राकृतिक संख्याओं का उपयोग किया जाता है , जो ये दर्शाता है और समान तुल्यता वर्ग हैं।[4]
संसाधन सीमाओं के साथ अधिक-एक कमी
अधिक-एक कमी अधिकांशतः संसाधन प्रतिबंधों के अधीन होती हैं, उदाहरण के लिए कि कमी फलन बहुपद समय, या परिपथ, या पॉलीलॉगरिदमिक अनुमान लघुगणकीय समिष्ट में गणना योग्य है जहां प्रत्येक बाद की कमी की धारणा पहले की तुलना में अशक्त है; विवरण के लिए बहुपद-समय में कमी और लॉग-स्पेस में कमी देखें।
निर्णय संबंधी समस्याओं को देखते हुए और और एक कलन विधि एन जो उदाहरणों को हल करता है , हम अधिक-एक कमी को का उपयोग कर सकते हैं उदाहरणों को हल करने के लिए का उपयोग करते है:
- N के लिए आवश्यक समय और कमी के लिए आवश्यक समय है
- N के लिए आवश्यक अधिकतम समिष्ट और कमी के लिए आवश्यक समिष्ट है
हम कहते हैं कि भाषाओं का एक वर्ग 'c ' (या प्राकृतिक संख्याओं के घात समुच्चय का एक उपसमूह) अधिक-एक न्यूनता के अनुसार बंद कर दिया जाता है यदि 'c' की किसी भाषा से 'c' के बाहर की भाषा में कोई कमी नहीं होती है। यदि किसी वर्ग को अधिक-एक न्यूनता के अंतर्गत बंद किया जाता है, जिससे अधिक-एक कमी का उपयोग यह दिखाने के लिए किया जा सकता है कि एक समस्या 'c' में एक समस्या को कम करके 'c' में है। अधिक-एक कमी मूल्यवान हैं क्योंकि अधिकांश अच्छी तरह से अध्ययन की गई जटिलता कक्षाएं कुछ प्रकार के अधिक-एक रिड्यूसिबिलिटी के अनुसार बंद होती हैं, जिनमें p (जटिलता), np (जटिलता), L (जटिलता), NL (जटिलता), सह-एनपी, पीएसपीएसीई सम्मिलित हैं। , ऍक्स्प, और अधिक अन्य उदाहरण के लिए यह ज्ञात है कि सूचीबद्ध पहले चार बहुभुज समय अनुमानों की बहुत अशक्त कमी धारणा तक बंद हैं। चूँकि, ये कक्षाएं सही विधि से अधिक-एक कमी के अनुसार बंद नहीं की गई हैं।
अधिक-एक कमी बढ़ाई गई
कोई अधिक-एक कमी के सामान्यीकृत स्थितियों के बारे में भी पूछ सकता है। ऐसा ही एक उदाहरण ई-रिडक्शन है, जहां हम विचार करते हैं जो पुनरावर्ती तक सीमित होने के अतिरिक्त पुनरावर्ती रूप से गणना योग्य हैं . परिणामी रिड्यूसिबिलिटी संबंध को दर्शाया गया है , और इसके पोसेट का अध्ययन ट्यूरिंग डिग्री के समान ही किया गया है। उदाहरण के लिए, एक जंप समुच्चय है ई-डिग्री के लिए ई-डिग्री ट्यूरिंग डिग्री के पोसेट से भिन्न कुछ गुणों को स्वीकार करती है, उदाहरण के लिए हीरे के ग्राफ को नीचे दी गई डिग्री में एम्बेड करता है .[5]
गुण
- अधिक-एक रिड्यूसिबिलिटी और 1-रिड्यूसिबिलिटी के संबंध (गणित) सकर्मक संबंध और रिफ्लेक्सिव संबंध हैं और इस प्रकार प्राकृतिक संख्याओं के पॉवरसेट पर एक प्रीऑर्डर प्रेरित करते हैं।
- यदि और केवल यदि है
- एक समुच्चय रुकने की समस्या के लिए अधिक-एक को कम करने योग्य है यदि और केवल यदि यह पुनरावर्ती रूप से गणना योग्य है। यह कहता है कि अधिक-एक न्यूनता के संबंध में, रुकने की समस्या सभी पुनरावर्ती रूप से गणना योग्य समस्याओं में सबसे जटिल है। इस प्रकार रुकने की समस्या पुनः है। ध्यान दें कि यह एकमात्र आर.ई. नहीं है।
- एक व्यक्तिगत ट्यूरिंग मशीन T (अर्थात, इनपुट का समुच्चय जिसके लिए T अंततः रुकती है) के लिए विशेष रुकने की समस्या अधिक-एक पूर्ण है यदि T एक सार्वभौमिक ट्यूरिंग मशीन है। एमिल पोस्ट ने दिखाया कि पुनरावर्ती रूप से असंख्य समुच्चय उपस्थित हैं जो न तो निर्णायकता (तर्क) और न ही एम-पूर्ण हैं, और इसलिए गैर-सार्वभौमिक ट्यूरिंग मशीनें उपस्थित हैं जिनकी व्यक्तिगत रुकने की समस्याएं फिर भी अनिर्णीत हैं।
कार्प में कमी
एक बहुपद-समय में कमी|बहुपद-समय में समस्या a से समस्या b में अधिक-एक कमी (जिनमें से दोनों को सामान्यतः निर्णय समस्याएं होने की आवश्यकता होती है) समस्या a में इनपुट को समस्या b में इनपुट में बदलने के लिए एक बहुपद-समय एल्गोरिदम है , जैसे कि रूपांतरित समस्या का आउटपुट मूल समस्या के समान होटी है। समस्या A के एक उदाहरण x को इस परिवर्तन को प्रयुक्त करके समस्या B का एक उदाहरण y उत्पन्न करके, समस्या B के लिए एल्गोरिदम में इनपुट के रूप में y देकर और उसका आउटपुट लौटाकर हल किया जा सकता है। बहुपद-समय अधिक-एक कमी को 'बहुपद परिवर्तन' या 'कार्प कमी' के रूप में भी जाना जा सकता है, जिसका नाम रिचर्ड कार्प के नाम पर रखा गया है। इस प्रकार की कमी को निम्न या द्वारा दर्शाया जाता है .[6][7]
संदर्भ
- ↑ 1.0 1.1 Abrahamson, Karl R. (Spring 2016). "मानचित्रण कटौती". CSCI 6420 – Computability and Complexity. East Carolina University. Retrieved 2021-11-12.
- ↑ E. L. Post, "Recursively enumerable sets of positive integers and their decision problems", Bulletin of the American Mathematical Society 50 (1944) 284–316
- ↑ Norman Shapiro, "Degrees of Computability", Transactions of the American Mathematical Society 82, (1956) 281–299
- ↑ 4.0 4.1 4.2 4.3 4.4 P. Odifreddi, Classical Recursion Theory: The theory of functions and sets of natural numbers (p.320). Studies in Logic and the Foundations of Mathematics, vol. 125 (1989), Elsevier 0-444-87295-7.
- ↑ S. Ahmad, Embedding the Diamond in the Enumeration Degrees (1991). Journal of Symbolic Logic, vol.56.
- ↑ Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective, Cambridge University Press, pp. 59–60, ISBN 9781139472746
- ↑ Kleinberg, Jon; Tardos, Éva (2006). Algorithm Design. Pearson Education. pp. 452–453. ISBN 978-0-321-37291-8.
