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

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

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

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

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

परिभाषाएँ

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

कल्पना करना और वर्णमाला (कंप्यूटर विज्ञान) पर औपचारिक भाषाएँ हैं $\Sigma$ और $\Gamma$, क्रमश। से अधिक-एक कमी $A$ को $B$ कुल गणना योग्य कार्य है $f:\Sigma ^{*}\rightarrow \Gamma ^{*}$ उसमें वह गुण है जो प्रत्येक शब्द में है में है यदि और केवल यदि में है $B$.

मान लीजिए कि $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

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

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

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

संसाधन सीमाओं के साथ कई-एक कटौती

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

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

• एन के लिए आवश्यक समय और कटौती के लिए आवश्यक समय
• N के लिए आवश्यक अधिकतम स्थान और कमी के लिए आवश्यक स्थान

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

कई-एक कटौती बढ़ाई गई

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

गुण

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

कार्प कटौती

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