अनेक न्यूनीकरण

कम्प्यूटेबिलिटी सिद्धांत और कम्प्यूटेशनल संगणना सिद्धांत में, अधिक-एक कमी (जिसे मैपिंग कमी भी कहा जाता है) एक कमी है जो एक निर्णय समस्या के उदाहरणों को परिवर्तित करती है (एक उदाहरण $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}$ को हल करता है

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

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

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

परिभाषाएँ

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

मान लीजिए कि $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$ रूप से समरूपी है

$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}$ का उप्योगुप्योग किया जाता है ^पृ.257

m-डिग्री के कुछ गुण, जिनमें से कुछ ट्यूरिंग डिग्री के अनुरूप गुणों से भिन्न हैं:^{पृ.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}$ का एक लक्षण वर्णन है जैसा कि अद्वितीय पोसेट अपने आइडियल (समुच्चय सिद्धांत) के अधिक स्पष्ट गुणों को संतुष्ट करता है, एक समान लक्षण वर्णन ट्यूरिंग डिग्री से दूर हो गया है।

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

संसाधन सीमाओं के साथ अधिक-एक कमी

अधिक-एक कमी अधिकांशतः संसाधन प्रतिबंधों के अधीन होती हैं, उदाहरण के लिए कि कमी फलन बहुपद समय, $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}^{'}$ समुच्चय है ई-डिग्री के लिए ई-डिग्री ट्यूरिंग डिग्री के पोसेट से भिन्न कुछ गुणों को स्वीकार करती है, उदाहरण के लिए हीरे के ग्राफ को नीचे दी गई डिग्री में एम्बेड करता है .

गुण

• अधिक-एक रिड्यूसिबिलिटी और 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$ द्वारा दर्शाया जाता है .