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

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

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

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

परिभाषाएँ

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

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

$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$.