अनेक न्यूनीकरण: 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"/>कई-एक कटौती के साथ, दैवज्ञ (अर्थात, बी के लिए हमारा समाधान) को अंत में केवल एक बार लागू किया जा सकता है, और उत्तर को संशोधित नहीं किया जा सकता है। इसका मतलब यह है कि यदि हम यह दिखाना चाहते हैं कि समस्या A को समस्या B में घटाया जा सकता है, तो हम B के लिए अपने समाधान का उपयोग A के समाधान में केवल एक बार कर सकते हैं, ट्यूरिंग कमी के विपरीत, जहां हम B के लिए अपने समाधान का उपयोग जितनी बार कर सकते हैं ए को हल करते समय आवश्यक है।
+अनेक न्यूनीकरण एक विशेष स्थिति है और ट्यूरिंग न्यूनीकरण का सशक्त रूप है।<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>f: \Sigma^{*}\rightarrow\Gamma^{*}</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>
 === प्राकृत संख्याओं का उपसमुच्चय ===
-दो सेट दिए गए <math>A,B \subseteq \mathbb{N}</math> हम कहते हैं <math>A</math> अधिक-एक को कम करने योग्य है <math>B</math> और लिखा
+दो समुच्चय दिए गए <math>A,B \subseteq \mathbb{N}</math> हम कहते हैं <math>A</math> और <math>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>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>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><sup>पृष्ठ 324</sup>
 :<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>\equiv_m</math> एक तुल्यता संबंध है, इसके तुल्यता वर्गों को एम-डिग्री कहा जाता है और एक पोसेट बनता है इस प्रकार <math>\mathcal D_m</math> द्वारा प्रेरित आदेश के साथ <math>\leq_m</math> का उप्योगुप्योग किया जाता है <ref name="Odifreddi89" /><sup>पृ.257</sup>
-एक सेट <math>B</math> यदि इसे अधिक-एक पूर्ण या केवल 'एम-पूर्ण' कहा जाता है <math>B</math> पुनरावर्ती रूप से गणना योग्य है और प्रत्येक पुनरावर्ती रूप से गणना योग्य सेट है <math>A</math> एम-रेड्यूसिबल है <math>B</math>.
+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_m</math> एक तुल्यता संबंध है, इसके तुल्यता वर्गों को एम-डिग्री कहा जाता है और एक पोसेट बनता है <math>\mathcal D_m</math> द्वारा प्रेरित आदेश के साथ <math>\leq_m</math>.<ref name="Odifreddi89" /><sup>पृ.257</sup>
-एम-डिग्री के कुछ गुण, जिनमें से कुछ [[ट्यूरिंग डिग्री]] के अनुरूप गुणों से भिन्न हैं:<ref name="Odifreddi89" /><sup>पृ.555--581</sup>
+<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" />
-* एम-डिग्री पर एक अच्छी तरह से परिभाषित जंप ऑपरेटर है।
-* जंप 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" /><sup>पृ. 574--575</sup>
+== संसाधन सीमाओं के साथ अनेक न्यूनीकरण                                                                                         ==
-<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" /><sup>पृष्ठ 325</sup>
+अनेक न्यूनीकरण अधिकांशतः संसाधन प्रतिबंधों के अधीन होती हैं, उदाहरण के लिए कि न्यूनीकरण फलन बहुपद समय, <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> का उपयोग करते है:
+* N के लिए आवश्यक समय और न्यूनीकरण के लिए आवश्यक समय है
+* N के लिए आवश्यक अधिकतम समिष्ट और न्यूनीकरण के लिए आवश्यक समिष्ट है
-कई-एक कटौती अक्सर संसाधन प्रतिबंधों के अधीन होती हैं, उदाहरण के लिए कि कमी फ़ंक्शन बहुपद समय, लघुगणकीय स्थान में गणना योग्य है <math>AC_0</math> या <math>NC_0</math> सर्किट, या पॉलीलॉगरिदमिक अनुमान जहां प्रत्येक बाद की कमी की धारणा पहले की तुलना में कमजोर है; विवरण के लिए [[बहुपद-समय में कमी]] और [[लॉग-स्पेस में कमी]] देखें।
+हम कहते हैं कि भाषाओं का एक वर्ग 'c ' (या प्राकृतिक संख्याओं के घात समुच्चय का एक उपसमूह) अनेक न्यूनता के अनुसार संवर्त कर दिया जाता है यदि 'c' की किसी भाषा से 'c' के बाहर की भाषा में कोई न्यूनीकरण नहीं होती है। यदि किसी वर्ग को अनेक न्यूनता के अंतर्गत संवर्त किया जाता है, जिससे अनेक न्यूनीकरण का उपयोग यह दिखाने के लिए किया जा सकता है कि एक समस्या 'c' में एक समस्या को कम करके 'c' में है। अनेक न्यूनीकरण मूल्यवान हैं क्योंकि अधिकांश अच्छी तरह से अध्ययन की गई सम्मिश्रता कक्षाएं कुछ प्रकार के अनेक रिड्यूसिबिलिटी के अनुसार संवर्त होती हैं, जिनमें [[पी (जटिलता)|p (सम्मिश्रता)]], [[एनपी (जटिलता)|np (सम्मिश्रता)]], L [[एल (जटिलता)|(सम्मिश्रता)]], [[एनएल (जटिलता)|NL (सम्मिश्रता)]], [[सह-एनपी]], पीएसपीएसीई सम्मिलित हैं। , [[EXP|ऍक्स्प]], और अधिक अन्य उदाहरण के लिए यह ज्ञात है कि सूचीबद्ध पहले चार बहुभुज समय अनुमानों की बहुत अशक्त न्यूनीकरण धारणा तक संवर्त हैं। चूँकि, ये कक्षाएं सही विधि से अनेक न्यूनीकरण के अनुसार संवर्त नहीं की गई हैं।
-निर्णय संबंधी समस्याओं को देखते हुए <math>A</math> और <math>B</math> और एक [[कलन विधि]] एन जो उदाहरणों को हल करता है <math>B</math>, हम अधिक-एक कमी का उपयोग कर सकते हैं <math>A</math> को <math>B</math> के उदाहरणों को हल करने के लिए <math>A</math> में:
+== अनेक न्यूनीकरण संवृदध                                                                                                                                                                                                              ==
-* एन के लिए आवश्यक समय और कटौती के लिए आवश्यक समय
+कोई अनेक न्यूनीकरण के सामान्यीकृत स्थितियों के बारे में भी पूछ सकता है। ऐसा ही एक उदाहरण ई-रिडक्शन है, जहां हम विचार करते हैं  जो <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>
-* N के लिए आवश्यक अधिकतम स्थान और कमी के लिए आवश्यक स्थान
-हम कहते हैं कि भाषाओं का एक वर्ग 'सी' (या प्राकृतिक संख्याओं के घात सेट का एक उपसमूह) कई-एक न्यूनता के तहत बंद कर दिया जाता है यदि 'सी' की किसी भाषा से 'सी' के बाहर की भाषा में कोई कमी नहीं होती है। यदि किसी वर्ग को अधिक-एक न्यूनता के अंतर्गत बंद किया जाता है, तो अधिक-एक कमी का उपयोग यह दिखाने के लिए किया जा सकता है कि एक समस्या 'सी' में एक समस्या को कम करके 'सी' में है। कई-एक कटौती मूल्यवान हैं क्योंकि अधिकांश अच्छी तरह से अध्ययन की गई जटिलता कक्षाएं कुछ प्रकार के कई-एक रिड्यूसिबिलिटी के तहत बंद होती हैं, जिनमें [[पी (जटिलता)]], [[एनपी (जटिलता)]], [[एल (जटिलता)]], [[एनएल (जटिलता)]], [[सह-एनपी]], पीएसपीएसीई शामिल हैं। , [[EXP]], और कई अन्य। उदाहरण के लिए यह ज्ञात है कि सूचीबद्ध पहले चार बहुभुज समय अनुमानों की बहुत कमजोर कमी धारणा तक बंद हैं। हालाँकि, ये कक्षाएं मनमाने ढंग से कई-एक कटौती के तहत बंद नहीं की गई हैं।
-== कई-एक कटौती बढ़ाई गई ==
-कोई अधिक-एक कमी के सामान्यीकृत मामलों के बारे में भी पूछ सकता है। ऐसा ही एक उदाहरण ई-रिडक्शन है, जहां हम विचार करते हैं <math>f:A\to B</math> जो पुनरावर्ती तक सीमित होने के बजाय पुनरावर्ती रूप से गणना योग्य हैं <math>f</math>. परिणामी रिड्यूसिबिलिटी संबंध को दर्शाया गया है <math>\leq_e</math>, और इसके पोसेट का अध्ययन ट्यूरिंग डिग्री के समान ही किया गया है। उदाहरण के लिए, एक जंप सेट है <math>\boldsymbol 0^'_e</math> ई-डिग्री के लिए। ई-डिग्री ट्यूरिंग डिग्री के पोसेट से भिन्न कुछ गुणों को स्वीकार करती है, उदाहरण के लिए। हीरे के ग्राफ को नीचे दी गई डिग्री में एम्बेड करना <math>\boldsymbol'_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:कमी (जटिलता)]]
 == गुण ==
-* कई-एक रिड्यूसिबिलिटी और 1-रिड्यूसिबिलिटी के [[संबंध (गणित)]] [[सकर्मक संबंध]] और रिफ्लेक्सिव संबंध हैं और इस प्रकार प्राकृतिक संख्याओं के [[ सत्ता स्थापित ]] पर एक [[पूर्व आदेश]] प्रेरित करते हैं।
+* अनेक रिड्यूसिबिलिटी और 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 के एक उदाहरण 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 81: / Line 82: @@
 }}
 </ref>
+== संदर्भ                                                                                                                                                                                                                                                                     ==
-== संदर्भ ==
 {{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