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

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

कटौती के प्रकार

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

अनेक-एक कटौती

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

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

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

ट्यूरिंग रिडक्शन

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

संपूर्णता

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

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

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

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

यह भी देखें

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

बाहरी संबंध

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