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

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