अनेक न्यूनीकरण: Difference between revisions

Latest revision as of 16:49, 29 August 2023

कम्प्यूटेबिलिटी सिद्धांत और कम्प्यूटेशनल संगणना सिद्धांत में, अनेक न्यूनीकरण (जिसे मैपिंग न्यूनीकरण ^[1] भी कहा जाता है) एक न्यूनीकरण है जो एक निर्णय समस्या के उदाहरणों को परिवर्तित करती है (एक उदाहरण $L_{1}$ में हो) एक अन्य निर्णय समस्या (चाहे एक उदाहरण $L_{2}$ ) में एक प्रभावी फलन का उपयोग कर रहा है। घटाया गया उदाहरण भाषा $L_{2}$ में है यदि और केवल यदि प्रारंभिक उदाहरण इसकी भाषा $L_{1}$ में है। इस प्रकार यदि हम यह तय कर सकते हैं कि $L_{2}$ उदाहरण $L_{2}$ भाषा में हैं या नहीं, तो हम न्यूनीकरण और समाधान प्रयुक्त करके यह तय कर सकते हैं कि $L_{1}$ उदाहरण इसकी भाषा में हैं या नहीं है $L_{2}$ . इस प्रकार, न्यूनीकरण का उपयोग दो समस्याओं की सापेक्ष कम्प्यूटेशनल कठिनाई को मापने के लिए किया जा सकता है। ऐसा कहा जाता है कि $L_{1}$ कम होकर $L_{2}$ हो जाता है, यदि समान व्यक्ति के शब्दों में $L_{2}$ को हल करना $L_{1}$ की तुलना में कठिन है। कहने का तात्पर्य यह है कि, $L_{2}$ को हल करने वाले किसी भी एल्गोरिदम का उपयोग (अन्यथा अपेक्षाकृत सरल) प्रोग्राम के भाग के रूप में भी किया जा सकता है जो $L_{1}$ को हल करता है

अनेक न्यूनीकरण एक विशेष स्थिति है और ट्यूरिंग न्यूनीकरण का सशक्त रूप है।^[1] अनेक न्यूनीकरण के साथ, दैवज्ञ (अर्थात, b के लिए हमारा समाधान) को अंत में केवल एक बार प्रयुक्त किया जा सकता है, और उत्तर को संशोधित नहीं किया जा सकता है। इसका कारण यह है कि यदि हम यह दिखाना चाहते हैं कि समस्या A को समस्या B में घटाया जा सकता है, तो हम B के लिए अपने समाधान का उपयोग A के समाधान में केवल एक बार कर सकते हैं, ट्यूरिंग न्यूनीकरण के विपरीत होते है, जहां हम B के लिए अपने समाधान का उपयोग जितनी बार कर सकते हैं a को हल करते समय आवश्यक है।

इसका कारण यह है कि अनेक न्यूनीकरण एक समस्या के उदाहरणों को दूसरी समस्या के उदाहरणों में मैप करती है, जबकि ट्यूरिंग न्यूनीकरण एक समस्या के समाधान की गणना करती है, यह मानते हुए कि दूसरी समस्या को हल करना सरल है। समस्याओं को अलग-अलग सम्मिश्रता वर्गों में अलग करने में अनेक न्यूनीकरण अधिक प्रभावी है। चूँकि, अनेक कटौतियों पर बढ़े हुए प्रतिबंधों से उन्हें खोजना अधिक कठिन हो गया है।

अनेक न्यूनीकरण का उपयोग पहली बार एमिल पोस्ट द्वारा 1944 में प्रकाशित एक पेपर में किया गया था।^[2] इसके पश्चात् नॉर्मन शापिरो ने 1956 में स्ट्रांग रिड्यूसिबिलिटी नाम से इसी अवधारणा का उपयोग किया था।^[3]

परिभाषाएँ

औपचारिक भाषाएँ

मान लीजिए कि $A$ और $B$ क्रमशः $\Sigma$ और $\Gamma$ वर्णमाला (कंप्यूटर विज्ञान) पर औपचारिक भाषाएँ हैं। $A$ को $B$ तक अनेक-एक न्यूनीकरण एक कुल गणना योग्य फलन है जिसमें यह गुण है कि प्रत्येक शब्द $w$ $A$ में है यदि और केवल यदि $f(w)$ $B$ में है

यदि ऐसा कोई फलन $f$ अस्तित्व में है, हम $A$ ऐसा कहते हैं $B$ अनेक कम करने योग्य या एम-कम करने योग्य है

A\leq _{\mathrm {m} }B.

प्राकृत संख्याओं का उपसमुच्चय

दो समुच्चय दिए गए $A,B\subseteq \mathbb {N}$ हम कहते हैं $A$ और $B$ कम करने योग्य है

A\leq _{\mathrm {m} }B

यदि कुल गणना योग्य फलन $f$ उपस्थित है इस प्रकार साथ $x\in A$ आईएफएफ $f(x)\in B$ . है यदि इसके अतिरिक्त $f$ विशेषण है, हम कहते हैं $A$ के लिए पुनरावर्ती $B$ रूप से समरूपी है ^[4]

A\equiv B

अनेक तुल्यता

यदि $A\leq _{\mathrm {m} }B\,\mathrm {and} \,B\leq _{\mathrm {m} }A$ हम कहते हैं इस प्रकार $A$ अनेक समतुल्य या m-समतुल्य $B$ है

A\equiv _{\mathrm {m} }B.

अनेक पूर्णता (एम-पूर्णता)

एक समुच्चय $B$ यदि इसे अनेक पूर्ण या केवल 'एम-पूर्ण' कहा जाता है इस प्रकार $B$ पुनरावर्ती रूप से गणना योग्य है और प्रत्येक पुनरावर्ती रूप से गणना योग्य समुच्चय है और $A$ एम-रेड्यूसिबल $B$ है .

डिग्री

$\equiv _{m}$ एक तुल्यता संबंध है, इसके तुल्यता वर्गों को एम-डिग्री कहा जाता है और एक पोसेट बनता है इस प्रकार ${\mathcal {D}}_{m}$ द्वारा प्रेरित आदेश के साथ $\leq _{m}$ का उप्योगुप्योग किया जाता है ^[4]^पृ.257

m-डिग्री के कुछ गुण, जिनमें से कुछ ट्यूरिंग डिग्री के अनुरूप गुणों से भिन्न हैं:^[4]^{पृ.555--581}

एम-डिग्री पर एक अच्छी तरह से परिभाषित जंप संचालक है।
जंप 0 के साथ एकमात्र 0_m-डिग्री' 0_mहै.
एम-डिग्री $\mathbf {a} >_{m}{\boldsymbol {0}}_{m}'$ हैं जहां अस्तित्व ही नहीं $\mathbf {b}$ है जहाँ $\mathbf {b} '=\mathbf {a}$ .
कम से कम तत्व के साथ प्रत्येक गणनीय रैखिक क्रम ${\mathcal {D}}_{m}$ में एम्बेड होता है .
${\mathcal {D}}_{m}$ का प्रथम क्रम सिद्धांत दूसरे क्रम के अंकगणित के सिद्धांत के लिए समरूपी है।

${\mathcal {D}}_{m}$ का एक लक्षण वर्णन है जैसा कि अद्वितीय पोसेट अपने आइडियल (समुच्चय सिद्धांत) के अधिक स्पष्ट गुणों को संतुष्ट करता है, एक समान लक्षण वर्णन ट्यूरिंग डिग्री से दूर हो गया है।^[4]

$\equiv _{1}$ एक समतुल्य संबंध है, और इसके समतुल्य वर्ग (जिन्हें 1-डिग्री कहा जाता है) एक स्थिति $\leq _{1}$ बनाते हैं माईहिल समरूपता प्रमेय|मायहिल समरूपता प्रमेय को सभी समुच्चयो के लिए कहा जा सकता है प्राकृतिक संख्याओं $A,B$ का उपयोग किया जाता है , जो ये $A\equiv B\iff A\equiv _{1}B$ दर्शाता है $\equiv$ और $\equiv _{1}$ समान तुल्यता वर्ग हैं।^[4]

संसाधन सीमाओं के साथ अनेक न्यूनीकरण

अनेक न्यूनीकरण अधिकांशतः संसाधन प्रतिबंधों के अधीन होती हैं, उदाहरण के लिए कि न्यूनीकरण फलन बहुपद समय, $AC_{0}$ या $NC_{0}$ परिपथ, या पॉलीलॉगरिदमिक अनुमान लघुगणकीय समिष्ट में गणना योग्य है जहां प्रत्येक बाद की न्यूनीकरण की धारणा पहले की तुलना में अशक्त है; विवरण के लिए बहुपद-समय में न्यूनीकरण और लॉग-स्पेस में न्यूनीकरण देखें।

निर्णय संबंधी समस्याओं को देखते हुए $A$ और $B$ और एक कलन विधि एन जो उदाहरणों $B$ को हल करता है , हम अनेक न्यूनीकरण $A$ को $B$ का उपयोग कर सकते हैं उदाहरणों को हल करने के लिए $A$ का उपयोग करते है:

N के लिए आवश्यक समय और न्यूनीकरण के लिए आवश्यक समय है
N के लिए आवश्यक अधिकतम समिष्ट और न्यूनीकरण के लिए आवश्यक समिष्ट है

हम कहते हैं कि भाषाओं का एक वर्ग 'c ' (या प्राकृतिक संख्याओं के घात समुच्चय का एक उपसमूह) अनेक न्यूनता के अनुसार संवर्त कर दिया जाता है यदि 'c' की किसी भाषा से 'c' के बाहर की भाषा में कोई न्यूनीकरण नहीं होती है। यदि किसी वर्ग को अनेक न्यूनता के अंतर्गत संवर्त किया जाता है, जिससे अनेक न्यूनीकरण का उपयोग यह दिखाने के लिए किया जा सकता है कि एक समस्या 'c' में एक समस्या को कम करके 'c' में है। अनेक न्यूनीकरण मूल्यवान हैं क्योंकि अधिकांश अच्छी तरह से अध्ययन की गई सम्मिश्रता कक्षाएं कुछ प्रकार के अनेक रिड्यूसिबिलिटी के अनुसार संवर्त होती हैं, जिनमें p (सम्मिश्रता), np (सम्मिश्रता), L (सम्मिश्रता), NL (सम्मिश्रता), सह-एनपी, पीएसपीएसीई सम्मिलित हैं। , ऍक्स्प, और अधिक अन्य उदाहरण के लिए यह ज्ञात है कि सूचीबद्ध पहले चार बहुभुज समय अनुमानों की बहुत अशक्त न्यूनीकरण धारणा तक संवर्त हैं। चूँकि, ये कक्षाएं सही विधि से अनेक न्यूनीकरण के अनुसार संवर्त नहीं की गई हैं।

अनेक न्यूनीकरण संवृदध

कोई अनेक न्यूनीकरण के सामान्यीकृत स्थितियों के बारे में भी पूछ सकता है। ऐसा ही एक उदाहरण ई-रिडक्शन है, जहां हम विचार करते हैं जो $f:A\to B$ पुनरावर्ती तक सीमित होने के अतिरिक्त पुनरावर्ती $f$ रूप से गणना योग्य हैं . परिणामी रिड्यूसिबिलिटी संबंध $\leq _{e}$ को दर्शाया गया है , और इसके पोसेट का अध्ययन ट्यूरिंग डिग्री के समान ही किया गया है। उदाहरण के लिए, एक जंप ${\boldsymbol {0}}_{e}^{'}$ समुच्चय है ई-डिग्री के लिए ई-डिग्री ट्यूरिंग डिग्री के पोसेट से भिन्न कुछ गुणों को स्वीकार करती है, उदाहरण के लिए हीरे के ग्राफ को नीचे दी गई डिग्री में एम्बेड करता है .^[5]

गुण

अनेक रिड्यूसिबिलिटी और 1-रिड्यूसिबिलिटी के संबंध (गणित) सकर्मक संबंध और रिफ्लेक्सिव संबंध हैं और इस प्रकार प्राकृतिक संख्याओं के पॉवरसेट पर एक प्रीऑर्डर प्रेरित करते हैं।
$A\leq _{\mathrm {m} }B$ यदि और केवल यदि $\mathbb {N} \setminus A\leq _{\mathrm {m} }\mathbb {N} \setminus B.$ है
एक समुच्चय रुकने की समस्या के लिए अनेक को कम करने योग्य है यदि और केवल यदि यह पुनरावर्ती रूप से गणना योग्य है। यह कहता है कि अनेक न्यूनता के संबंध में, रुकने की समस्या सभी पुनरावर्ती रूप से गणना योग्य समस्याओं में सबसे जटिल है। इस प्रकार रुकने की समस्या पुनः है। ध्यान दें कि यह एकमात्र आर.ई. नहीं है।
एक व्यक्तिगत ट्यूरिंग मशीन T (अर्थात, इनपुट का समुच्चय जिसके लिए T अंततः रुकती है) के लिए विशेष रुकने की समस्या अनेक पूर्ण है यदि T एक सार्वभौमिक ट्यूरिंग मशीन है। एमिल पोस्ट ने दिखाया कि पुनरावर्ती रूप से असंख्य समुच्चय उपस्थित हैं जो न तो निर्णायकता (तर्क) और न ही एम-पूर्ण हैं, और इसलिए गैर-सार्वभौमिक ट्यूरिंग मशीनें उपस्थित हैं जिनकी व्यक्तिगत रुकने की समस्याएं फिर भी अनिर्णीत हैं।

कार्प में न्यूनीकरण

एक बहुपद-समय में न्यूनीकरण|बहुपद-समय में समस्या a से समस्या b में अनेक न्यूनीकरण (जिनमें से दोनों को सामान्यतः निर्णय समस्याएं होने की आवश्यकता होती है) समस्या a में इनपुट को समस्या b में इनपुट में बदलने के लिए एक बहुपद-समय एल्गोरिदम है , जैसे कि रूपांतरित समस्या का आउटपुट मूल समस्या के समान होटी है। समस्या A के एक उदाहरण x को इस परिवर्तन को प्रयुक्त करके समस्या B का एक उदाहरण y उत्पन्न करके, समस्या B के लिए एल्गोरिदम में इनपुट के रूप में y देकर और उसका आउटपुट लौटाकर हल किया जा सकता है। बहुपद-समय अनेक न्यूनीकरण को 'बहुपद परिवर्तन' या 'कार्प न्यूनीकरण' के रूप में भी जाना जा सकता है, जिसका नाम रिचर्ड कार्प के नाम पर रखा गया है। इस प्रकार की न्यूनीकरण को निम्न $A\leq _{m}^{P}B$ या $A\leq _{p}B$ द्वारा दर्शाया जाता है .^[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 $\Sigma _{2}$ 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.

[Abrahamson2016-1] 1.0 ^1.1 Abrahamson, Karl R. (Spring 2016). "मानचित्रण कटौती". CSCI 6420 – Computability and Complexity. East Carolina University. Retrieved 2021-11-12.

[2] E. L. Post, "Recursively enumerable sets of positive integers and their decision problems", Bulletin of the American Mathematical Society 50 (1944) 284–316

[3] Norman Shapiro, "Degrees of Computability", Transactions of the American Mathematical Society 82, (1956) 281–299

[Odifreddi89-4] 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.

[5] S. Ahmad, Embedding the Diamond in the $\Sigma _{2}$ Enumeration Degrees (1991). Journal of Symbolic Logic, vol.56.

[goldreich-6] Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective, Cambridge University Press, pp. 59–60, ISBN 9781139472746

[kleinberg-tardos-7] Kleinberg, Jon; Tardos, Éva (2006). Algorithm Design. Pearson Education. pp. 452–453. ISBN 978-0-321-37291-8.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

@@ Line 1: / Line 1: @@
 {{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_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">{{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_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 को हल करते समय आवश्यक है।
+अनेक न्यूनीकरण एक विशेष स्थिति है और ट्यूरिंग न्यूनीकरण का सशक्त रूप है।<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>
+अनेक न्यूनीकरण का उपयोग पहली बार [[एमिल पोस्ट]] द्वारा 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>
 == परिभाषाएँ                                                                                 ==
 === औपचारिक भाषाएँ ===
-मान लीजिए कि <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> में है
-यदि ऐसा कोई फलन <math>f</math> अस्तित्व में है, हम <math>A</math> ऐसा कहते हैं <math>B</math> अधिक-एक कम करने योग्य या एम-कम करने योग्य है
+यदि ऐसा कोई फलन <math>f</math> अस्तित्व में है, हम <math>A</math> ऐसा कहते हैं <math>B</math> अनेक कम करने योग्य या एम-कम करने योग्य है
 :<math>A \leq_{\mathrm{m}} B.</math>
 === प्राकृत संख्याओं का उपसमुच्चय ===
@@ Line 21: / Line 21: @@
 यदि कुल गणना योग्य फलन <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 \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>B</math> यदि इसे अधिक-एक पूर्ण या केवल 'एम-पूर्ण' कहा जाता है इस प्रकार <math>B</math> पुनरावर्ती रूप से गणना योग्य है और प्रत्येक पुनरावर्ती रूप से गणना योग्य समुच्चय है और <math>A</math> एम-रेड्यूसिबल <math>B</math> है .
+एक समुच्चय <math>B</math> यदि इसे अनेक पूर्ण या केवल 'एम-पूर्ण' कहा जाता है इस प्रकार <math>B</math> पुनरावर्ती रूप से गणना योग्य है और प्रत्येक पुनरावर्ती रूप से गणना योग्य समुच्चय है और <math>A</math> एम-रेड्यूसिबल <math>B</math> है .
 ==डिग्री                                                                                                                                                                                                              ==
@@ Line 43: / Line 43: @@
 <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>AC_0</math> या <math>NC_0</math> परिपथ, या पॉलीलॉगरिदमिक अनुमान लघुगणकीय समिष्ट में गणना योग्य है जहां प्रत्येक बाद की न्यूनीकरण की धारणा पहले की तुलना में अशक्त है; विवरण के लिए [[बहुपद-समय में कमी|बहुपद-समय में न्यूनीकरण]] और [[लॉग-स्पेस में कमी|लॉग-स्पेस में न्यूनीकरण]] देखें।
-निर्णय संबंधी समस्याओं को देखते हुए <math>A</math> और <math>B</math> और एक [[कलन विधि]] एन जो उदाहरणों <math>B</math> को हल करता है , हम अधिक-एक कमी <math>A</math> को <math>B</math> का उपयोग कर सकते हैं उदाहरणों को हल करने के लिए <math>A</math> का उपयोग करते है:
+निर्णय संबंधी समस्याओं को देखते हुए <math>A</math> और <math>B</math> और एक [[कलन विधि]] एन जो उदाहरणों <math>B</math> को हल करता है , हम अनेक न्यूनीकरण <math>A</math> को <math>B</math> का उपयोग कर सकते हैं उदाहरणों को हल करने के लिए <math>A</math> का उपयोग करते है:
-* N के लिए आवश्यक समय और कमी के लिए आवश्यक समय है
+* N के लिए आवश्यक समय और न्यूनीकरण के लिए आवश्यक समय है
-* N के लिए आवश्यक अधिकतम समिष्ट और कमी के लिए आवश्यक समिष्ट है
+* N के लिए आवश्यक अधिकतम समिष्ट और न्यूनीकरण के लिए आवश्यक समिष्ट है
-हम कहते हैं कि भाषाओं का एक वर्ग 'c ' (या प्राकृतिक संख्याओं के घात समुच्चय का एक उपसमूह) अधिक-एक न्यूनता के अनुसार संवर्त कर दिया जाता है यदि 'c' की किसी भाषा से 'c' के बाहर की भाषा में कोई कमी नहीं होती है। यदि किसी वर्ग को अधिक-एक न्यूनता के अंतर्गत संवर्त किया जाता है, जिससे अधिक-एक कमी का उपयोग यह दिखाने के लिए किया जा सकता है कि एक समस्या 'c' में एक समस्या को कम करके 'c' में है। अधिक-एक कमी मूल्यवान हैं क्योंकि अधिकांश अच्छी तरह से अध्ययन की गई जटिलता कक्षाएं कुछ प्रकार के अधिक-एक रिड्यूसिबिलिटी के अनुसार संवर्त होती हैं, जिनमें [[पी (जटिलता)|p (जटिलता)]], [[एनपी (जटिलता)|np (जटिलता)]], L [[एल (जटिलता)|(जटिलता)]], [[एनएल (जटिलता)|NL (जटिलता)]], [[सह-एनपी]], पीएसपीएसीई सम्मिलित हैं। , [[EXP|ऍक्स्प]], और अधिक अन्य उदाहरण के लिए यह ज्ञात है कि सूचीबद्ध पहले चार बहुभुज समय अनुमानों की बहुत अशक्त कमी धारणा तक संवर्त हैं। चूँकि, ये कक्षाएं सही विधि से अधिक-एक कमी के अनुसार संवर्त नहीं की गई हैं।
+हम कहते हैं कि भाषाओं का एक वर्ग '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>
+[[Category:Created On 08/07/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:कमी (जटिलता)]]
-== अधिक-एक कमी बढ़ाई गई                                                                                                                                                                                                              ==
-कोई अधिक-एक कमी के सामान्यीकृत स्थितियों के बारे में भी पूछ सकता है। ऐसा ही एक उदाहरण ई-रिडक्शन है, जहां हम विचार करते हैं  जो <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-रिड्यूसिबिलिटी के [[संबंध (गणित)]] [[सकर्मक संबंध]] और रिफ्लेक्सिव संबंध हैं और इस प्रकार प्राकृतिक संख्याओं के [[ सत्ता स्थापित |पॉवरसेट]] पर एक [[पूर्व आदेश|प्रीऑर्डर]] प्रेरित करते हैं।
+* अनेक रिड्यूसिबिलिटी और 1-रिड्यूसिबिलिटी के [[संबंध (गणित)]] [[सकर्मक संबंध]] और रिफ्लेक्सिव संबंध हैं और इस प्रकार प्राकृतिक संख्याओं के [[ सत्ता स्थापित |पॉवरसेट]] पर एक [[पूर्व आदेश|प्रीऑर्डर]] प्रेरित करते हैं।
 * <math>A \leq_{\mathrm{m}} B</math> [[अगर और केवल अगर|यदि और केवल यदि]] <math>\mathbb{N} \setminus A \leq_{\mathrm{m}} \mathbb{N} \setminus B.</math> है
-* एक समुच्चय [[रुकने की समस्या]] के लिए अधिक-एक को कम करने योग्य है यदि और केवल यदि यह [[पुनरावर्ती रूप से गणना योग्य]] है। यह कहता है कि अधिक-एक न्यूनता के संबंध में, रुकने की समस्या सभी पुनरावर्ती रूप से गणना योग्य समस्याओं में सबसे जटिल है। इस प्रकार रुकने की समस्या पुनः है। ध्यान दें कि यह एकमात्र आर.ई. नहीं है।
+* एक समुच्चय [[रुकने की समस्या]] के लिए अनेक को कम करने योग्य है यदि और केवल यदि यह [[पुनरावर्ती रूप से गणना योग्य]] है। यह कहता है कि अनेक न्यूनता के संबंध में, रुकने की समस्या सभी पुनरावर्ती रूप से गणना योग्य समस्याओं में सबसे जटिल है। इस प्रकार रुकने की समस्या पुनः है। ध्यान दें कि यह एकमात्र आर.ई. नहीं है।
-* एक व्यक्तिगत ट्यूरिंग मशीन T (अर्थात, इनपुट का समुच्चय जिसके लिए T अंततः रुकती है) के लिए विशेष रुकने की समस्या अधिक-एक पूर्ण है यदि T एक सार्वभौमिक ट्यूरिंग मशीन है। एमिल पोस्ट ने दिखाया कि पुनरावर्ती रूप से असंख्य समुच्चय उपस्थित हैं जो न तो निर्णायकता (तर्क) और न ही एम-पूर्ण हैं, और इसलिए गैर-सार्वभौमिक ट्यूरिंग मशीनें उपस्थित हैं जिनकी व्यक्तिगत रुकने की समस्याएं फिर भी अनिर्णीत हैं।
+* एक व्यक्तिगत ट्यूरिंग मशीन 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
+एक बहुपद-समय में न्यूनीकरण|बहुपद-समय में समस्या 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
 |publisher=Pearson Education
@@ Line 72: / Line 84: @@
 == संदर्भ                                                                                                                                                                                                                                                                     ==
 {{reflist}}
-[[Category: कमी (जटिलता)]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 08/07/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:कमी (जटिलता)]]

Anonymous

Search

अनेक न्यूनीकरण: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 16:49, 29 August 2023

Contents

परिभाषाएँ

औपचारिक भाषाएँ

प्राकृत संख्याओं का उपसमुच्चय

अनेक तुल्यता

अनेक पूर्णता (एम-पूर्णता)

डिग्री

संसाधन सीमाओं के साथ अनेक न्यूनीकरण

अनेक न्यूनीकरण संवृदध

गुण

कार्प में न्यूनीकरण

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

अनेक न्यूनीकरण: Difference between revisions

Latest revision as of 16:49, 29 August 2023

परिभाषाएँ

औपचारिक भाषाएँ

प्राकृत संख्याओं का उपसमुच्चय

अनेक तुल्यता

अनेक पूर्णता (एम-पूर्णता)

डिग्री

संसाधन सीमाओं के साथ अनेक न्यूनीकरण

अनेक न्यूनीकरण संवृदध

गुण

कार्प में न्यूनीकरण

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories