कमी (जटिलता)

बूलियन संतुष्टि समस्या (A ∨ B) ∧ (¬A ∨ ¬B ∨ ¬C) ∧ (¬A ∨ B ∨ C) से वर्टेक्स कवर समस्या में कमी का उदाहरण। नीले कोने एक न्यूनतम शीर्ष आवरण बनाते हैं, और ग्रे अंडाकार में नीले कोने मूल सूत्र के लिए एक संतोषजनक सत्य असाइनमेंट के अनुरूप होते हैं।

कम्प्यूटेबिलिटी सिद्धांत और कम्प्यूटेशनल जटिलता सिद्धांत में, एक कमी एक कम्प्यूटेशनल समस्या को दूसरी समस्या में बदलने के लिए एक कलन विधि है। एक समस्या से दूसरी समस्या में पर्याप्त रूप से कुशल कमी का उपयोग यह दिखाने के लिए किया जा सकता है कि दूसरी समस्या कम से कम उतनी ही कठिन है जितनी पहली।

सहज रूप से, समस्या ए समस्या बी के लिए कम करने योग्य है, यदि समस्या बी को कुशलता से हल करने के लिए एक एल्गोरिथ्म (यदि यह अस्तित्व में है) को समस्या ए को हल करने के लिए सबरूटीन के रूप में भी इस्तेमाल किया जा सकता है। कुशलता से। जब यह सत्य है, तो A को हल करना B को हल करने से कठिन नहीं हो सकता। कठिन का अर्थ है किसी दिए गए संदर्भ में आवश्यक कम्प्यूटेशनल संसाधनों का उच्च अनुमान (जैसे, उच्च समय जटिलता, अधिक मेमोरी आवश्यकता, एकल-थ्रेडेड समाधान की तुलना में समानांतर समाधान के लिए अतिरिक्त हार्डवेयर प्रोसेसर कोर की महंगी आवश्यकता, आदि)। ए से बी तक की कमी के अस्तित्व को शॉर्टहैंड नोटेशन ए में लिखा जा सकता है ≤_m बी, आमतौर पर उपयोग की जाने वाली कमी के प्रकार को इंगित करने के लिए ≤ पर एक सबस्क्रिप्ट के साथ (एम: मैपिंग कमी, पी: बहुपद कमी)।

एक विशेष प्रकार की कटौती से समस्याओं के एक सेट पर उत्पन्न गणितीय संरचना आम तौर पर एक पूर्व आदेश बनाती है, जिसका समकक्ष वर्ग ट्यूरिंग डिग्री और जटिलता वर्गों को परिभाषित करने के लिए इस्तेमाल किया जा सकता है।

परिचय

दो मुख्य स्थितियाँ हैं जहाँ हमें कटौती का उपयोग करने की आवश्यकता है:

सबसे पहले, हम स्वयं को एक ऐसी समस्या को हल करने का प्रयास करते हुए पाते हैं जो उस समस्या के समान है जिसे हम पहले ही हल कर चुके हैं। इन मामलों में, अक्सर नई समस्या को हल करने का एक त्वरित तरीका नई समस्या के प्रत्येक उदाहरण को पुरानी समस्या के उदाहरणों में बदलना है, इन्हें हमारे मौजूदा समाधान का उपयोग करके हल करें, और फिर अंतिम समाधान प्राप्त करने के लिए इनका उपयोग करें। यह शायद कटौती का सबसे स्पष्ट उपयोग है।
दूसरा: मान लीजिए कि हमारे पास एक समस्या है जिसे हमने हल करना कठिन साबित कर दिया है, और हमारे पास एक समान नई समस्या है। हमें संदेह हो सकता है कि इसे हल करना भी कठिन है। हम विरोधाभास से बहस करते हैं: मान लीजिए कि नई समस्या को हल करना आसान है। फिर, अगर हम दिखा सकते हैं कि पुरानी समस्या के हर उदाहरण को नई समस्या के उदाहरणों में बदलकर और उन्हें हल करके आसानी से हल किया जा सकता है, तो हमारे पास एक विरोधाभास है। यह स्थापित करता है कि नई समस्या भी कठिन है।

कमी का एक बहुत ही सरल उदाहरण गुणन से वर्ग तक है। मान लीजिए कि हम केवल यह जानते हैं कि कैसे जोड़ना, घटाना, वर्ग लेना और दो से विभाजित करना है। हम किन्हीं भी दो संख्याओं का गुणनफल प्राप्त करने के लिए, निम्न सूत्र के साथ संयुक्त ज्ञान का उपयोग कर सकते हैं:

a\times b={\frac {\left(\left(a+b\right)^{2}-a^{2}-b^{2}\right)}{2}}

हमारे पास दूसरी दिशा में भी कमी है; स्पष्ट रूप से, यदि हम दो संख्याओं का गुणा कर सकते हैं, तो हम एक संख्या का वर्ग कर सकते हैं। ऐसा लगता है कि ये दोनों समस्याएं समान रूप से कठिन हैं। इस तरह की कमी ट्यूरिंग कमी से मेल खाती है।

हालाँकि, कमी बहुत कठिन हो जाती है यदि हम प्रतिबंध जोड़ते हैं कि हम केवल एक बार स्क्वेरिंग फ़ंक्शन का उपयोग कर सकते हैं, और केवल अंत में। इस मामले में, भले ही हमें गुणन सहित सभी बुनियादी अंकगणितीय संक्रियाओं का उपयोग करने की अनुमति हो, सामान्य रूप से कोई कमी मौजूद नहीं है, क्योंकि एक वर्ग के रूप में वांछित परिणाम प्राप्त करने के लिए हमें पहले इसके वर्गमूल की गणना करनी होगी, और यह वर्ग जड़ एक अपरिमेय संख्या हो सकती है जैसे ${\sqrt {2}}$ जिसे परिमेय संख्याओं पर अंकगणितीय संक्रियाओं द्वारा निर्मित नहीं किया जा सकता है। दूसरी दिशा में जा रहे हैं, हालांकि, हम निश्चित रूप से केवल अंत में केवल एक गुणा के साथ एक संख्या को वर्ग कर सकते हैं। कमी के इस सीमित रूप का उपयोग करते हुए, हमने आश्चर्यजनक परिणाम दिखाया है कि गुणा वर्ग की तुलना में सामान्य रूप से कठिन है। यह कई-एक कमी के अनुरूप है।

गुण

एक कमी एक प्रीऑर्डरिंग है, जो कि P(N)×P(N) पर एक प्रतिवर्त संबंध और सकर्मक संबंध है, जहां P(N) प्राकृतिक संख्याओं का सत्ता स्थापित है।

कटौती के प्रकार और अनुप्रयोग

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

एक जटिलता वर्ग के लिए एक समस्या पूर्ण (जटिलता) है यदि कक्षा की प्रत्येक समस्या उस समस्या को कम करती है, और यह कक्षा में भी है। इस अर्थ में समस्या वर्ग का प्रतिनिधित्व करती है, क्योंकि इसका कोई भी समाधान, कटौती के संयोजन में, कक्षा में हर समस्या को हल करने के लिए इस्तेमाल किया जा सकता है।

हालांकि, उपयोगी होने के लिए, कटौती आसान होनी चाहिए। उदाहरण के लिए, एक मुश्किल-से-सुलझाने वाली एनपी-पूर्ण समस्या को कम करना काफी संभव है, जैसे बूलियन संतुष्टि समस्या को एक तुच्छ समस्या, जैसे कि यह निर्धारित करना कि क्या कोई संख्या शून्य के बराबर है, कमी मशीन होने से समस्या को घातीय समय और आउटपुट शून्य में हल करें समाधान होने पर ही। हालाँकि, इससे बहुत कुछ हासिल नहीं होता है, क्योंकि भले ही हम नई समस्या को हल कर सकते हैं, कमी को पूरा करना उतना ही कठिन है जितना कि पुरानी समस्या को हल करना। इसी तरह, एक संगणनीय कार्य की गणना में कमी एक अनिर्णीत समस्या को एक निर्णायक समस्या तक कम कर सकती है। जैसा कि माइकल सिप्सर गणना के सिद्धांत के परिचय में बताते हैं: कक्षा में विशिष्ट समस्याओं की जटिलता के सापेक्ष कमी आसान होनी चाहिए [...] यदि कमी की गणना करना मुश्किल था, तो पूरी समस्या का एक आसान समाधान आवश्यक रूप से इसे कम करने वाली समस्याओं का आसान समाधान नहीं मिलेगा।

इसलिए, कमी की उपयुक्त धारणा अध्ययन की जा रही जटिलता वर्ग पर निर्भर करती है। जटिलता वर्ग एनपी (जटिलता) और बहुपद पदानुक्रम जैसे कठिन वर्गों का अध्ययन करते समय, बहुपद-समय में कटौती का उपयोग किया जाता है। पी के भीतर कक्षाओं का अध्ययन करते समय जैसे एनसी (जटिलता) और एनएल (जटिलता), लॉग-स्पेस कटौती का उपयोग किया जाता है। कम्प्यूटेबिलिटी सिद्धांत में कटौती का उपयोग यह दिखाने के लिए भी किया जाता है कि क्या समस्याएं मशीनों द्वारा हल करने योग्य हैं या नहीं; इस मामले में कटौती केवल संगणनीय कार्यों तक ही सीमित है।

अनुकूलन (अधिकतमकरण या न्यूनीकरण) समस्याओं के मामले में, हम अक्सर सन्निकटन-संरक्षण कमी के संदर्भ में सोचते हैं। मान लीजिए कि हमारे पास दो अनुकूलन समस्याएं हैं जैसे कि एक समस्या के उदाहरणों को दूसरे के उदाहरणों पर मैप किया जा सकता है, इस तरह से बाद की समस्या के उदाहरणों के लगभग इष्टतम समाधानों को पूर्व में लगभग इष्टतम समाधान प्राप्त करने के लिए परिवर्तित किया जा सकता है। इस तरह, यदि हमारे पास एक अनुकूलन एल्गोरिथ्म (या सन्निकटन एल्गोरिथ्म) है जो समस्या बी के उदाहरणों के निकट-इष्टतम (या इष्टतम) समाधान ढूंढता है, और समस्या ए से समस्या बी तक एक कुशल सन्निकटन-संरक्षण कमी, संरचना द्वारा हम एक अनुकूलन प्राप्त करते हैं एल्गोरिथम जो समस्या ए के उदाहरणों के निकट-इष्टतम समाधान देता है। सन्निकटन-संरक्षण कटौती अक्सर सन्निकटन परिणामों की कठोरता को साबित करने के लिए उपयोग की जाती है: यदि कुछ अनुकूलन समस्या ए अनुमानित करना कठिन है (कुछ जटिलता धारणा के तहत) कुछ के लिए α से बेहतर कारक के भीतर α, और समस्या A से समस्या B तक एक β-सन्निकटन-संरक्षण कमी है, हम यह निष्कर्ष निकाल सकते हैं कि कारक α/β के भीतर समस्या B का अनुमान लगाना कठिन है।

उदाहरण

यह दिखाने के लिए कि एक निर्णय समस्या P अनिर्णीत समस्या है, हमें एक निर्णय समस्या से कमी का पता लगाना चाहिए जो पहले से ही P के लिए अनिर्णनीय है। वह कमी कार्य एक गणना योग्य कार्य होना चाहिए। विशेष रूप से, हम अक्सर दिखाते हैं कि एक समस्या P अनिर्णीत है, यह दिखाते हुए कि रुकने की समस्या P तक कम हो जाती है।
जटिलता वर्ग पी (जटिलता), एनपी (जटिलता) और पीएसपीएसीई (अनेक-एक, कार्प) बहुपद-समय कटौती के तहत बंद हैं।
जटिलता वर्ग एल (जटिलता), एनएल (जटिलता), पी (जटिलता), एनपी (जटिलता) और पीएसपीएसीई लॉग-स्पेस कमी के तहत बंद हैं।

विस्तृत उदाहरण

निम्नलिखित उदाहरण से पता चलता है कि यह साबित करने के लिए कि एक भाषा अनिर्णायक है, हॉल्टिंग समस्या से कमी का उपयोग कैसे किया जाए। मान लीजिए कि एच (एम, डब्ल्यू) यह निर्धारित करने की समस्या है कि दी गई ट्यूरिंग मशीन एम इनपुट स्ट्रिंग डब्ल्यू पर (स्वीकार या अस्वीकार करके) रुकती है या नहीं। यह भाषा अनिर्णीत मानी जाती है। मान लीजिए E(M) यह निर्धारित करने की समस्या है कि दी गई ट्यूरिंग मशीन M द्वारा स्वीकार की गई भाषा खाली है (दूसरे शब्दों में, क्या M किसी भी तार को स्वीकार करता है)। हम दिखाते हैं कि H से घटाकर E अनिर्णीत है।

एक विरोधाभास प्राप्त करने के लिए, मान लें कि R, E के लिए एक निर्णायक है। हम इसका उपयोग H के लिए एक निर्णायक S बनाने के लिए करेंगे (जिसे हम जानते हैं कि मौजूद नहीं है)। दिए गए इनपुट एम और डब्ल्यू (एक ट्यूरिंग मशीन और कुछ इनपुट स्ट्रिंग), निम्नलिखित व्यवहार के साथ एस (एम, डब्ल्यू) को परिभाषित करें: एस एक ट्यूरिंग मशीन एन बनाता है जो केवल तभी स्वीकार करता है जब इनपुट स्ट्रिंग एन डब्ल्यू है और एम इनपुट डब्ल्यू पर रुकता है , और अन्यथा नहीं रुकता। निर्णायक एस अब यह जांचने के लिए आर (एन) का मूल्यांकन कर सकता है कि एन द्वारा स्वीकृत भाषा खाली है या नहीं। यदि R, N को स्वीकार करता है, तो N द्वारा स्वीकार की गई भाषा खाली है, इसलिए विशेष रूप से M, इनपुट w पर रुकता नहीं है, इसलिए S अस्वीकार कर सकता है। यदि R, N को अस्वीकार करता है, तो N द्वारा स्वीकृत भाषा खाली नहीं है, इसलिए M इनपुट w पर रुकता है, इसलिए S स्वीकार कर सकता है। इस प्रकार, यदि हमारे पास E के लिए एक निर्णायक R था, तो हम किसी भी मशीन M और इनपुट w के लिए हॉल्टिंग समस्या H(M, w) के लिए एक निर्णायक S का उत्पादन करने में सक्षम होंगे। चूँकि हम जानते हैं कि ऐसा S मौजूद नहीं हो सकता है, यह इस प्रकार है कि भाषा E भी अनिर्णीत है।

यह भी देखें

संदर्भ

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, MIT Press, 2001, ISBN 978-0-262-03293-3
Hartley Rogers, Jr.: Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967, ISBN 978-0-262-68052-3.
Peter Bürgisser: Completeness and Reduction in Algebraic Complexity Theory, Springer, 2000, ISBN 978-3-540-66752-0.
E.R. Griffor: Handbook of Computability Theory, North Holland, 1999, ISBN 978-0-444-89882-1.