एनपी-कठोरता
कम्प्यूटेशनल जटिलता सिद्धांत में, एनपी-कठोरता (एनपी (जटिलता) | गैर-नियतात्मक बहुपद-समय की कठोरता) समस्याओं के वर्ग की परिभाषित संपत्ति है जो अनौपचारिक रूप से कम से कम एनपी (जटिलता) में सबसे कठिन समस्याओं के रूप में कठिन हैं। एनपी-हार्ड समस्या का सरल उदाहरण सबसेट योग समस्या है।
एक अधिक सटीक विनिर्देश है: समस्या 'एच' एनपी-हार्ड है जब एनपी में हर समस्या 'एल' बहुपद समय में 'एच' में कमी (जटिलता) हो सकती है; अर्थात्, H के लिए हल मानकर 1 इकाई समय लगता है, H'बहुपद समय में L को हल करने के लिए s समाधान का उपयोग किया जा सकता है।[1][2] नतीजतन, किसी भी एनपी-हार्ड समस्या को हल करने के लिए बहुपद समय एल्गोरिदम ढूंढना एनपी में सभी समस्याओं के लिए बहुपद समय एल्गोरिदम प्रदान करेगा। जैसा कि संदेह है कि पी बनाम एनपी | पी≠एनपी, यह संभावना नहीं है कि ऐसा एल्गोरिदम मौजूद है।[3] यह संदेह है कि एनपी-हार्ड समस्याओं के लिए कोई बहुपद-समय एल्गोरिदम नहीं हैं, लेकिन यह सिद्ध नहीं हुआ है।[4] इसके अलावा, कक्षा पी (जटिलता), जिसमें बहुपद समय में सभी समस्याओं को हल किया जा सकता है, एनपी (जटिलता) वर्ग में निहित है।[5]
परिभाषा
एक निर्णय समस्या एच एनपी-हार्ड है जब एनपी में हर समस्या एल के लिए, बहुत-एक कमी है | बहुपद-समय कई-एक कमी एल से एच तक।[1]: 80 एक समतुल्य परिभाषा की आवश्यकता है कि एनपी में हर समस्या एल को बहुपद समय में ओरेकल मशीन द्वारा एच के लिए ओरेकल के साथ हल किया जा सकता है।[6] अनौपचारिक रूप से, एल्गोरिथ्म के बारे में सोचा जा सकता है जो एच को हल करने के लिए ऐसी ऑरेकल मशीन को सबरूटीन के रूप में कॉल करता है और एल को बहुपद समय में हल करता है यदि सबरूटीन कॉल गणना करने के लिए केवल कदम लेता है।
एक और परिभाषा की आवश्यकता है कि एनपी-पूर्ण समस्या जी से एच तक बहुपद-समय की कमी हो।[1]: 91 चूंकि एनपी में कोई समस्या एल बहुपद समय में जी को कम कर देता है, एल बदले में बहुपद समय में एच को कम कर देता है, इसलिए यह नई परिभाषा पिछले का तात्पर्य है। अजीब तरह से, यह वर्ग एनपी-हार्ड को निर्णय समस्याओं तक सीमित नहीं करता है, और इसमें खोज समस्याएं या अनुकूलन समस्याएं भी शामिल हैं।
परिणाम
यदि पी ≠ एनपी, तो एनपी-हार्ड समस्याओं को बहुपद समय में हल नहीं किया जा सका।
कुछ एनपी-हार्ड ऑप्टिमाइज़ेशन समस्याएं कुछ स्थिर सन्निकटन अनुपात (विशेष रूप से, एपीएक्स में) या यहां तक कि किसी भी सन्निकटन अनुपात (बहुपद-समय सन्निकटन योजना में # जटिलता वर्ग या बहुपद के रूप में) तक बहुपद-समय सन्निकटन एल्गोरिथ्म हो सकती हैं। समय सन्निकटन योजना#नियतात्मक)।
उदाहरण
एनपी-हार्ड समस्या का उदाहरण निर्णय सबसेट योग समस्या है: पूर्णांकों का सेट दिया गया है, क्या उनमें से कोई गैर-खाली सबसेट शून्य तक जोड़ता है? यह निर्णय समस्या है और एनपी-पूर्ण होती है। एनपी-हार्ड समस्या का और उदाहरण भारित ग्राफ के सभी नोड्स के माध्यम से कम से कम लागत वाले चक्रीय मार्ग को खोजने की अनुकूलन समस्या है। इसे आमतौर पर ट्रैवलिंग सेल्समैन की समस्या के रूप में जाना जाता है।[7] ऐसी निर्णय समस्याएं हैं जो एनपी-हार्ड हैं लेकिन एनपी-पूर्ण नहीं हैं जैसे कि रुकने की समस्या। यही वह समस्या है जो प्रोग्राम और उसके इनपुट के बारे में पूछती है, क्या यह हमेशा के लिए चलेगा? यह हां/नहीं प्रश्न है और इसलिए निर्णय समस्या है। यह साबित करना आसान है कि रुकने की समस्या एनपी-कठिन है लेकिन एनपी-पूर्ण नहीं है। उदाहरण के लिए, बूलियन संतुष्टि की समस्या को ट्यूरिंग मशीन के विवरण में बदलकर हॉल्टिंग समस्या में कम किया जा सकता है जो सभी सत्य मान असाइनमेंट की कोशिश करती है और जब उसे कोई ऐसा मिल जाता है जो सूत्र को संतुष्ट करता है तो वह रुक जाता है और अन्यथा यह अनंत लूप में चला जाता है। यह देखना भी आसान है कि रुकने की समस्या एनपी में नहीं है क्योंकि एनपी में सभी समस्याएं संचालन की सीमित संख्या में निर्णायक होती हैं, लेकिन सामान्य तौर पर रुकने की समस्या अनिर्णीत समस्या है। ऐसी एनपी-हार्ड समस्याएं भी हैं जो न तो एनपी-पूर्ण हैं और न ही अनिर्णीत हैं। उदाहरण के लिए, सही परिमाणित बूलियन सूत्रों की भाषा पीएसपीएसीई में निर्णायक है, लेकिन गैर-नियतात्मक बहुपद समय में नहीं (जब तक कि एनपी = पीएसपीएसीई)।[8]
एनपी-नामकरण सम्मेलन
एनपी-कठिन समस्याओं को जटिलता वर्ग एनपी का तत्व नहीं होना चाहिए। चूंकि एनपी कम्प्यूटेशनल जटिलता सिद्धांत में केंद्रीय भूमिका निभाता है, इसे कई वर्गों के आधार के रूप में प्रयोग किया जाता है: एनपी (जटिलता): कम्प्यूटेशनल निर्णय समस्याओं का वर्ग जिसके लिए किसी दिए गए हाँ-समाधान को बहुपद समय में नियतात्मक ट्यूरिंग मशीन (या बहुपद समय में गैर-नियतात्मक ट्यूरिंग मशीन द्वारा हल करने योग्य) द्वारा समाधान के रूप में सत्यापित किया जा सकता है। एनपी-हार्ड: समस्याओं का वर्ग जो कम से कम एनपी में सबसे कठिन समस्याओं के रूप में कठिन हैं। समस्याएँ जो एनपी-हार्ड हैं उन्हें एनपी के तत्व होने की आवश्यकता नहीं है; वास्तव में, वे निर्णायक भी नहीं हो सकते हैं। एनपी-पूर्ण: निर्णय समस्याओं का वर्ग जिसमें एनपी में सबसे कठिन समस्याएं हैं। प्रत्येक एनपी-पूर्ण समस्या को एनपी में होना चाहिए।
- एनपी-आसान
- एनपी जितना कठिन है, लेकिन एनपी में जरूरी नहीं है।
एनपी-समतुल्य: निर्णय समस्याएं जो एनपी-हार्ड और एनपी-आसान दोनों हैं, लेकिन जरूरी नहीं कि एनपी में हों। एनपी-इंटरमीडिएट: यदि पी और एनपी अलग हैं, तो एनपी के क्षेत्र में निर्णय की समस्याएं मौजूद हैं जो पी और एनपी-पूर्ण समस्याओं के बीच आती हैं। (यदि पी और एनपी ही वर्ग हैं, तो एनपी-मध्यवर्ती समस्याएं मौजूद नहीं हैं क्योंकि इस मामले में प्रत्येक एनपी-पूर्ण समस्या पी में आती है, और परिभाषा के अनुसार, एनपी में प्रत्येक समस्या को एनपी-पूर्ण समस्या में घटाया जा सकता है। )
आवेदन क्षेत्र
एनपी-हार्ड समस्याओं को अक्सर नियम-आधारित भाषाओं से निपटाया जाता है जिनमें निम्न शामिल हैं:
- अनुमानित कंप्यूटिंग
- विन्यास प्रबंधन
- क्रिप्टोग्राफी
- डेटा खनन
- निर्णय समर्थन प्रणाली
- फाइलोजेनेटिक्स
- योजना
- प्रक्रिया निगरानी और नियंत्रण
- रोस्टर या शेड्यूल
- रूटिंग / वाहन रूटिंग
- अनुसूची
संदर्भ
- ↑ 1.0 1.1 1.2 Leeuwen, Jan van, ed. (1998). Handbook of Theoretical Computer Science. Vol. A, Algorithms and complexity. Amsterdam: Elsevier. ISBN 0262720140. OCLC 247934368.
- ↑ Knuth, Donald (1974). "Postscript about NP-hard problems". ACM SIGACT News. 6 (2): 15–16. doi:10.1145/1008304.1008305. S2CID 46480926.
- ↑ Daniel Pierre Bovet; Pierluigi Crescenzi (1994). Introduction to the Theory of Complexity. Prentice Hall. p. 69. ISBN 0-13-915380-2.
- ↑ "Shtetl-Optimized » Blog Archive » The Scientific Case for P≠NP". www.scottaaronson.com. Retrieved 2016-09-25.
- ↑ "PHYS771 Lecture 6: P, NP, and Friends". www.scottaaronson.com. Retrieved 2016-09-25.
- ↑ V. J. Rayward-Smith (1986). A First Course in Computability. Blackwell. p. 159. ISBN 0-632-01307-9.
- ↑ Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H. G.; Shmoys, D. B. (1985), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley & Sons, ISBN 0-471-90413-9.
- ↑ More precisely, this language is PSPACE-complete; see, for example, Wegener, Ingo (2005), Complexity Theory: Exploring the Limits of Efficient Algorithms, Springer, p. 189, ISBN 9783540210450.
- Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5.
