पूरक (जटिलता)
कम्प्यूटेशनल जटिलता सिद्धांत में, निर्णय समस्या का पूरक 'हां' और 'नहीं' उत्तरों को उलटने से उत्पन्न निर्णय समस्या है।[1] समतुल्य रूप से, यदि हम निर्णय समस्याओं को परिमित तारों के सेट के रूप में परिभाषित करते हैं, तो कुछ निश्चित डोमेन पर इस सेट का पूरक (सेट सिद्धांत) इसकी पूरक समस्या है।[2] उदाहरण के लिए, एक महत्वपूर्ण समस्या यह है कि क्या संख्या एक अभाज्य संख्या है। इसका पूरक यह निर्धारित करना है कि क्या कोई संख्या एक समग्र संख्या है (एक संख्या जो अभाज्य नहीं है)। यहाँ पूरक का प्रांत एक से अधिक सभी पूर्णांकों का समुच्चय है।[3] हर समस्या से उसकी पूरक समस्या में ट्यूरिंग कमी होती है।[4] पूरक संक्रिया एक अंतर्वलन (गणित) है, जिसका अर्थ है कि यह स्वयं को नष्ट कर देता है, या पूरक का पूरक मूल समस्या है।
कोई इसे एक जटिलता वर्ग के पूरक के लिए सामान्यीकृत कर सकता है, जिसे पूरक वर्ग कहा जाता है, जो कक्षा में हर समस्या के पूरक का सेट है।[5] यदि किसी वर्ग को C कहा जाता है, तो उसके पूरक को पारंपरिक रूप से co-C लेबल किया जाता है। ध्यान दें कि यह समस्याओं के एक समूह के रूप में जटिलता वर्ग का पूरक नहीं है, जिसमें बहुत अधिक समस्याएं होंगी।
एक वर्ग को 'पूरक के तहत बंद' कहा जाता है यदि कक्षा में किसी समस्या का पूरक अभी भी कक्षा में है।[6] क्योंकि हर समस्या से लेकर उसके पूरक तक ट्यूरिंग रिडक्शन हैं, ट्यूरिंग रिडक्शन के तहत बंद होने वाला कोई भी वर्ग पूरक के तहत बंद है। कोई भी वर्ग जो पूरक के तहत बंद है, उसके पूरक वर्ग के बराबर है। हालांकि, कई-एक कटौती के तहत, कई महत्वपूर्ण वर्गों, विशेष रूप से एनपी (जटिलता) को उनके पूरक वर्गों से अलग माना जाता है (हालांकि यह साबित नहीं हुआ है)।[7] ट्यूरिंग रिडक्शन के तहत किसी भी जटिलता वर्ग का समापन (गणित) उस वर्ग का सुपरसेट है जो पूरक के तहत बंद है। पूरक के तहत बंद होना सबसे छोटा वर्ग है। यदि किसी वर्ग को उसके पूरक के साथ प्रतिच्छेद किया जाता है, तो हमें एक (संभवतः खाली) उपसमुच्चय प्राप्त होता है जो पूरक के तहत बंद होता है।
प्रत्येक नियतात्मक जटिलता वर्ग (DSPACE(f(n)), DTIME(f(n)) सभी f(n) के लिए) पूरक के तहत बंद है,[8] क्योंकि कोई भी एल्गोरिथ्म में एक अंतिम चरण जोड़ सकता है जो उत्तर को उलट देता है। यह गैर-नियतात्मक जटिलता वर्गों के लिए काम नहीं करता है, क्योंकि यदि दोनों अभिकलन पथ मौजूद हैं जो स्वीकार करते हैं और पथ जो अस्वीकार करते हैं, और सभी पथ उनके उत्तर को उलट देते हैं, तब भी ऐसे पथ होंगे जो स्वीकार करते हैं और पथ जो अस्वीकार करते हैं - फलस्वरूप, मशीन में स्वीकार करता है दोनों घटनायें।
इसी तरह, संभाव्य वर्ग जैसे बीपीपी (जटिलता), जेडपीपी (जटिलता), बीक्यूपी या पीपी (जटिलता) जिन्हें उनके हां के संबंध में सममित रूप से परिभाषित किया गया है और पूरक के तहत बंद नहीं हैं। इसके विपरीत, आरपी (जटिलता) और 'सह-आरपी' जैसी कक्षाएं अपनी संभावनाओं को एकतरफा त्रुटि के साथ परिभाषित करती हैं, और इसलिए पूरक के तहत बंद नहीं हैं (वर्तमान में ज्ञात हैं)।
तिथि करने के लिए दिखाए गए सबसे आश्चर्यजनक जटिलता परिणामों में से कुछ ने दिखाया कि जटिलता वर्ग एनएल (जटिलता) और एसएल (जटिलता) वास्तव में पूरक के तहत बंद हैं, जबकि पहले यह व्यापक रूप से माना जाता था कि वे नहीं थे (इम्मरमैन-स्ज़ेलेपेसेनी प्रमेय देखें)। उत्तरार्द्ध अब कम आश्चर्यजनक हो गया है कि हम जानते हैं कि 'एसएल' 'एल (जटिलता)' के बराबर है, जो एक नियतात्मक वर्ग है।
प्रत्येक वर्ग जो स्वयं के लिए निम्न (जटिल) है, पूरक के अंतर्गत बंद है।
संदर्भ
- ↑ Itô, Kiyosi (1993), Encyclopedic Dictionary of Mathematics, Volume 1, MIT Press, p. 269, ISBN 9780262590204.
- ↑ Schrijver, Alexander (1998), Theory of Linear and Integer Programming, Wiley Series in Discrete Mathematics & Optimization, John Wiley & Sons, p. 19, ISBN 9780471982326.
- ↑ Homer, Steven; Selman, Alan L. (2011), Computability and Complexity Theory, Texts in Computer Science, Springer, ISBN 9781461406815.
- ↑ Singh, Arindama (2009), Elements of Computation Theory, Texts in Computer Science, Springer, Exercise 9.10, p. 287, ISBN 9781848824973.
- ↑ Bovet, Daniele; Crescenzi, Pierluigi (1994), Introduction to the Theory of Complexity, Prentice Hall International Series in Computer Science, Prentice Hall, pp. 133–134, ISBN 9780139153808.
- ↑ Vollmer, Heribert (1999), Introduction to Circuit Complexity: A Uniform Approach, Texts in Theoretical Computer Science. An EATCS Series, Springer, p. 113, ISBN 9783540643104.
- ↑ Pruim, R.; Wegener, Ingo (2005), Complexity Theory: Exploring the Limits of Efficient Algorithms, Springer, p. 66, ISBN 9783540274773.
- ↑ Ausiello, Giorgio (1999), Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer, p. 189, ISBN 9783540654315.
