बहुपद-समय में कमी

कम्प्यूटेशनल जटिलता सिद्धांत में एक बहुपद-समय में कमी एक समस्या को दूसरे का उपयोग करके हल करने की एक विधि है। एक से पता चलता है कि यदि दूसरी समस्या को हल करने वाला एक काल्पनिक सबरूटीन उपस्थित है तो पहली समस्या को दूसरी समस्या के लिए इनपुट में परिवर्तित या घटाकर (जटिलता) करके और सबरूटीन को एक या अधिक बार कॉल करके हल किया जा सकता है। यदि पहली समस्या को दूसरी समस्या में बदलने के लिए आवश्यक समय और सबरूटीन को जितनी बार कहा जाता है वह बहुपद है तो पहली समस्या बहुपद-समय को दूसरी तक कम करने योग्य है।

एक बहुपद-समय में कमी यह सिद्ध करती है कि पहली समस्या दूसरी समस्या से अधिक कठिन नहीं है क्योंकि जब भी दूसरी समस्या के लिए एक कुशल कलन विधि उपस्थित होता है तो पहली समस्या के लिए भी उपस्थित होता है। विरोधाभास से यदि पहली समस्या के लिए कोई कुशल एल्गोरिदम उपस्थित नहीं है तो दूसरे के लिए भी कोई अस्तित्व नहीं है। जटिलता वर्ग और उन वर्गों के लिए पूर्ण समस्याओं दोनों को परिभाषित करने के लिए बहुपद-समय की अल्पीकरण अधिकांशतः जटिलता सिद्धांत में उपयोग की जाती है।

अल्पीकरण के प्रकार

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

अनेक-एक अल्पीकरण

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

सत्य तालिका में कमी

समस्या A से समस्या B (दोनों निर्णय समस्याएं) में एक बहुपद-समय की सत्य-सारणी में कमी एक बहुपद समय एल्गोरिदम है जो इनपुट को समस्या A में इनपुट की एक निश्चित संख्या में समस्या B में बदलने के लिए है, जैसे कि मूल समस्या के लिए आउटपुट B के लिए आउटपुट के एक फलन के रूप में व्यक्त किया जा सकता है। A के लिए आउटपुट में B के लिए आउटपुट मैप करने वाला फलन सभी इनपुट के लिए समान होना चाहिए जिससे इसे सत्य तालिका द्वारा व्यक्त किया जा सकता है । इस प्रकार की कमी को अभिव्यक्ति $A\leq _{tt}^{P}B$ द्वारा निरूपित किया जा सकता है .

ट्यूरिंग अल्पीकरण

एक समस्या A से एक समस्या B तक एक बहुपद-समय ट्यूरिंग कमी एक एल्गोरिदम है जो समस्या B के लिए एक सबरूटीन को कॉल की बहुपद संख्या और उन सबरूटीन कॉल के बाहर बहुपद समय का उपयोग करके समस्या A को हल करती है। पॉलीनोमियल-टाइम ट्यूरिंग अल्पीकरण को 'कुक अल्पीकरण' के नाम से भी जाना जाता है, जिसका नाम स्टीफन कुक के नाम पर रखा गया है। इस प्रकार की कमी को अभिव्यक्ति $A\leq _{T}^{P}B$ द्वारा निरूपित किया जा सकता है अनेक-एक अल्पीकरण को ट्यूरिंग अल्पीकरण के प्रतिबंधित प्रकार के रूप में माना जा सकता है जहां समस्या B के लिए सबरूटीन में की गई कॉल की संख्या पूर्ण रूप से एक है और अल्पीकरण द्वारा लौटाया गया मान वही है जो सबरूटीन द्वारा लौटाया गया है।

संपूर्णता

किसी दिए गए जटिलता वर्ग C'और कमी ≤ के लिए एक पूर्ण समस्या एक समस्या P ' है जो C से संबंधित है, जैसे कि C में हर समस्या A में कमी A ≤ P है . उदाहरण के लिए एक समस्या NP-पूर्ण | NP-पूर्ण है यदि यह NP (जटिलता) से संबंधित है और NP में सभी समस्याओं में बहुपद-समय की कई-एक कमी है। एक समस्या जो NP से संबंधित है एक ज्ञात NP-पूर्ण समस्या से एक एकल बहुपद-बार कई-एक कमी को खोजने के द्वारा NP-पूर्ण सिद्ध हो सकती है। पी स्पेस-पूर्ण

औपचारिक भाषा और एक्सपटाइम-पूर्ण भाषाओं सहित अन्य जटिलता वर्गों के लिए पूर्ण समस्याओं को परिभाषित करने के लिए बहुपद-समय कई-एक अल्पीकरण का उपयोग किया गया है।

P (जटिलता) में हर निर्णय समस्या (बहुपद-समय की निर्णय समस्याओं का वर्ग) को हर दूसरी गैर-तुच्छ निर्णय समस्या में कम किया जा सकता है (जहां गैर-तुच्छ का अर्थ है कि हर इनपुट का एक ही आउटपुट नहीं है) एक बहुपद-समय कई-एक कमी से . समस्या ' A को 'B' में बदलने के लिए, बहुपद समय में 'A ' को हल करें, और फिर अलग-अलग उत्तरों के साथ समस्या 'B' के दो उदाहरणों में से एक को चुनने के लिए समाधान का उपयोग करें। इसलिए, P के अंदर जटिलता वर्गों जैसे L, NL, NC, और P स्वयं के लिए बहुपद-समय में अल्पीकरण का उपयोग पूर्ण भाषाओं को परिभाषित करने के लिए नहीं किया जा सकता है: यदि उनका उपयोग इस तरह से किया जाता है, तो प्रत्येक गैर-तुच्छ P में समस्या पूरी होगी। इसके अतिरिक्त लॉग-स्पेस अल्पीकरण या NC अल्पीकरण जैसे अशक्त अल्पीकरण का उपयोग इन वर्गों के लिए पूर्ण समस्याओं जैसे P-पूर्ण समस्याओं के वर्गों को परिभाषित करने के लिए किया जाता है।।

जटिलता वर्गों को परिभाषित करना

जटिलता वर्ग एनपी, पी स्पेस, और एक्सपटाइम की परिभाषाओं में अल्पीकरण सम्मिलित नहीं है: इन वर्गों के लिए पूर्ण भाषाओं की परिभाषा में अल्पीकरण केवल उनके अध्ययन में आती है। चूँकि कुछ स्थिति में एक जटिलता वर्ग को अल्पीकरण द्वारा परिभाषित किया जा सकता है। यदि C कोई निर्णय समस्या है तो कोई जटिलता वर्ग C को परिभाषित कर सकता है जिसमें A भाषाएं सम्मिलित हैं जिसके लिए $A\leq _{m}^{P}C$. इस स्थिति में C स्वचालित रूप से 'C ' के लिए पूर्ण हो जाएगा, किंतु 'C ' में अन्य पूर्ण समस्याएं भी हो सकती हैं।

इसका एक उदाहरण वास्तविकता के अस्तित्व सिद्धांत से परिभाषित जटिलता वर्ग $\exists \mathbb {R}$ है एक कम्प्यूटेशनल समस्या जिसे NP-हार्ड और पीएसपीएसीई में जाना जाता है, किंतु NP पीएसपीएसीई के लिए पूर्ण होने के लिए ज्ञात नहीं है या बहुपद पदानुक्रम में कोई भी भाषा $\exists \mathbb {R}$ समस्याओं का समूह है जिसमें वास्तविकताओं के अस्तित्वपरक सिद्धांत में बहुपद-समय बहु-एक कमी है; इसमें कई अन्य पूर्ण समस्याएँ हैं जैसे कि एक अप्रत्यक्ष ग्राफ़ की सीधीरेखीय क्रॉसिंग संख्या निर्धारित करना$\exists \mathbb {R}$ में प्रत्येक समस्या पी स्पेस से संबंधित संपत्ति को इनहेरिट करती है, और प्रत्येक $\exists \mathbb {R}$-पूर्ण समस्या NP-हार्ड है।

इसी तरह जटिलता वर्ग GI (जटिलता) में ऐसी समस्याएं सम्मिलित हैं जिन्हें ग्राफ समरूपता समस्या में कम किया जा सकता है। चूंकि ग्राफ समरूपता NP और सह-AM (जटिलता) दोनों से संबंधित है इस वर्ग की हर समस्या के लिए भी यही सच है। एक समस्या GI-पूर्ण है यदि यह इस वर्ग के लिए पूर्ण है ग्राफ समरूपता समस्या स्वयं GI-पूर्ण है जैसा कि कई अन्य संबंधित समस्याएं हैं।

यह भी देखें

• कार्प की 21 एनपी -पूर्ण समस्याएं

बाहरी संबंध

• MIT OpenCourseWare: 16. Complexity: P, NP, NP-completeness, Reductions