पूरक (जटिलता)
कम्प्यूटेशनल जटिलता सिद्धांत में निर्णय समस्या का पूरक 'हां' और 'नहीं' उत्तरों को उलटने से उत्पन्न निर्णय समस्या है।[1] समतुल्य रूप से यदि हम निर्णय समस्याओं को परिमित तारों के सेट के रूप में परिभाषित करते हैं, तो कुछ निश्चित डोमेन पर इस सेट का पूरक (सेट सिद्धांत) इसकी पूरक समस्या है।[2]
उदाहरण के लिए एक महत्वपूर्ण समस्या यह है कि क्या संख्या एक अभाज्य संख्या है। इसका पूरक यह निर्धारित करना है कि क्या कोई संख्या एक समग्र संख्या है (एक संख्या जो अभाज्य नहीं है)। यहाँ पूरक का प्रांत एक से अधिक सभी पूर्णांकों का समुच्चय है।[3]
हर समस्या से उसकी पूरक समस्या में ट्यूरिंग कमी होती है।[4] पूरक संक्रिया एक अंतर्वलन (गणित) है जिसका अर्थ है कि यह स्वयं को नष्ट कर देता है या पूरक का पूरक मूल समस्या है।
कोई इसे एक जटिलता वर्ग के पूरक के लिए सामान्यीकृत कर सकता है जिसे पूरक वर्ग कहा जाता है जो कक्षा में हर समस्या के पूरक का सेट है।[5] यदि किसी वर्ग को C कहा जाता है तो उसके पूरक को पारंपरिक रूप से co-C लेबल किया जाता है। ध्यान दें कि यह समस्याओं के एक समूह के रूप में जटिलता वर्ग का पूरक नहीं है जिसमें बहुत अधिक समस्याएं होंगी।
एक वर्ग को 'पूरक के तहत बंद' कहा जाता है यदि कक्षा में किसी समस्या का पूरक अभी भी कक्षा में है।[6] क्योंकि हर समस्या से लेकर उसके पूरक तक ट्यूरिंग रिडक्शन हैं, ट्यूरिंग रिडक्शन के तहत बंद होने वाला कोई भी वर्ग पूरक के तहत बंद है। कोई भी वर्ग जो पूरक के तहत बंद है, उसके पूरक वर्ग के समान है। चूँकि , कई-एक रिडक्शन के तहत कई महत्वपूर्ण वर्गों विशेष रूप से एनपी (जटिलता) को उनके पूरक वर्गों से अलग माना जाता है (चूँकि यह सिद्ध नहीं हुआ है)।[7]
ट्यूरिंग रिडक्शन के तहत किसी भी जटिलता वर्ग का समापन (गणित) उस वर्ग का सुपरसेट है जो पूरक के तहत बंद है। पूरक के तहत बंद होना सबसे छोटा वर्ग है। यदि किसी वर्ग को उसके पूरक के साथ प्रतिच्छेद किया जाता है तो हमें एक (संभवतः खाली) उपसमुच्चय प्राप्त होता है जो पूरक के तहत बंद होता है।
प्रत्येक नियतात्मक जटिलता वर्ग (DSPACE(f(n)), DTIME(f(n)) सभी f(n)) के लिए पूरक के तहत बंद है[8] क्योंकि कोई भी एल्गोरिथ्म में एक अंतिम चरण जोड़ सकता है जो उत्तर को उत्क्रम देता है। यह गैर-नियतात्मक जटिलता वर्गों के लिए काम नहीं करता है, क्योंकि यदि दोनों अभिकलन पथ उपस्थित हैं जो स्वीकार करते हैं और पथ जो अस्वीकार करते हैं और सभी पथ उनके उत्तर को उत्क्रम देते हैं तब भी ऐसे पथ होंगे जो स्वीकार करते हैं और पथ जो अस्वीकार करते हैं - परिणामस्वरूप मशीन दोनों स्थितियों में स्वीकार करती है।
इसी तरह, बीपीपी, जेडपीपी, बीक्यूपी या पीपी जैसे संभाव्य वर्ग जो उनके हां के संबंध में सममित रूप से परिभाषित होते हैं और पूरक के अंतर्गत बंद नहीं होते हैं। इसके विपरीत RP और सह-RP जैसी कक्षाएं अपनी संभावनाओं को एक पक्ष परिभाषित करती हैं और इसलिए पूरक के तहत बंद (वर्तमान में ज्ञात) नहीं हैं।
तिथि करने के लिए दिखाए गए सबसे आश्चर्यजनक जटिलता परिणामों में से कुछ ने दिखाया कि जटिलता वर्ग एनएल (जटिलता) और एसएल (जटिलता) वास्तव में पूरक के अंतर्गत बंद हैं, जबकि पहले यह व्यापक रूप से माना जाता था कि वे नहीं थे (इम्मरमैन-स्ज़ेलेपेसेनी प्रमेय देखें) उत्तरार्द्ध अब कम आश्चर्यजनक हो गया है कि हम जानते हैं कि 'SL ' 'L (जटिलता)' के समान है जो एक नियतात्मक वर्ग है।
प्रत्येक वर्ग जो स्वयं के लिए निम्न (जटिल) है पूरक के अंतर्गत बंद है।
संदर्भ
- ↑ 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.
