न्यूनीकरण (जटिलता)

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

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

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

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

परिचय

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

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

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

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

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

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

गुण

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

रिडक्शन के प्रकार और अनुप्रयोग

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

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

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

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

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

उदाहरण

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

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

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

एक विरोधाभास प्राप्त करने के लिए, मान लें कि R, E के लिए एक निर्णायक है। हम इसका उपयोग H के लिए एक निर्णायक S बनाने के लिए करेंगे (जिसे हम जानते हैं कि उपस्थित नहीं है)। दिए गए इनपुट m और w (एक ट्यूरिंग मशीन और कुछ इनपुट स्ट्रिंग), निम्नलिखित व्यवहार के साथ s (m, w) को परिभाषित करें: s एक ट्यूरिंग मशीन n बनाता है जो केवल तभी स्वीकार करता है जब इनपुट स्ट्रिंग n w है और m इनपुट w पर रुकता है , और अन्यथा नहीं रुकता है। निर्णायक s अब यह जांचने के लिए आर (n) का मूल्यांकन कर सकता है कि n द्वारा स्वीकृत भाषा है या नहीं है। यदि 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.