एनपी-कठोरता
कम्प्यूटेशनल सम्मिश्र सिद्धांत में, एनपी-कठोरता (एनपी (सम्मिश्र)) या गैर-नियतात्मक बहुपद-समय की कठोरता) समस्याओं के वर्ग की परिभाषित संपत्ति है जो अनौपचारिक रूप से कम से कम एनपी (सम्मिश्र) में सबसे कठिन समस्याओं के रूप में कठिन हैं। एनपी-हार्ड समस्या का सरल उदाहरण उपसमुच्चय योग समस्या है।
एक अधिक स्पष्ट विनिर्देश है: समस्या 'H' एनपी-हार्ड है जब एनपी में हर समस्या 'L' बहुपद समय में 'H' में कमी हो सकती है; अर्थात्, H के लिए हल मानकर 1 इकाई समय लगता है, H'बहुपद समय में L को हल करने के लिए s समाधान का उपयोग किया जा सकता है।[1][2] इस प्रकार परिणाम , किसी भी एनपी-हार्ड समस्या को हल करने के लिए बहुपद समय एल्गोरिदम खोजना एनपी में सभी समस्याओं के लिए बहुपद समय एल्गोरिदम प्रदान करता है। जैसा कि संदेह है कि P बनाम एनपी या P≠एनपी, यह संभावना नहीं है कि ऐसा एल्गोरिदम उपस्थित है।[3]
यह संदेह है कि एनपी-हार्ड समस्याओं के लिए कोई बहुपद-समय एल्गोरिदम नहीं हैं, किन्तु यह सिद्ध नहीं हुआ है।[4] इस प्रकार इसके अतिरिक्त, कक्षा P (सम्मिश्र), जिसमें बहुपद समय में सभी समस्याओं को हल किया जा सकता है, एनपी (सम्मिश्र) वर्ग में निहित है।[5]
परिभाषा
एक निर्णय समस्या H एनपी-हार्ड है जब एनपी में हर समस्या L के लिए, बहुत-एक कमी है | बहुपद-समय कई-एक कमी L से H तक होते है।[1]: 80 एक समतुल्य परिभाषा की आवश्यकता है कि एनपी में हर समस्या L को बहुपद समय में ओरेकल मशीन द्वारा H के लिए ओरेकल के साथ हल किया जा सकता है।[6] अनौपचारिक रूप से, एल्गोरिथ्म के बारे में सोचा जा सकता है जो H को हल करने के लिए ऐसी ऑरेकल मशीन को सबरूटीन के रूप में कॉल करता है और L को बहुपद समय में हल करता है यदि सबरूटीन कॉल गणना करने के लिए केवल कदम लेता है।
एक और परिभाषा की आवश्यकता है कि एनपी-पूर्ण समस्या जी से H तक बहुपद-समय की कमी होटी है।[1]: 91 चूंकि एनपी में कोई समस्या L बहुपद समय में जी को कम कर देता है, इस प्रकार L बदले में बहुपद समय में H को कम कर देता है, इसलिए यह नई परिभाषा पिछले का तात्पर्य है। यह वर्ग एनपी-हार्ड को निर्णय समस्याओं तक सीमित नहीं करता है, और इसमें खोज समस्याएं या अनुकूलन समस्याएं भी सम्मिलित हैं।
परिणाम
यदि P ≠ एनपी, तो एनपी-हार्ड समस्याओं को बहुपद समय में हल नहीं किया जा सकता था।
कुछ एनपी-हार्ड अनुकूलन समस्याएं बहुपद-समय पर कुछ स्थिर सन्निकटन अनुपात (विशेष रूप से, एपीएक्स में) या यहां तक कि किसी सन्निकटन अनुपात (पीटीएएस या एफपीटीएएस में) तक अनुमानित हो सकती हैं।
उदाहरण
एनपी-हार्ड समस्या का उदाहरण निर्णय उपसमुच्चय योग समस्या है: पूर्णांकों का सेट दिया गया है, क्या उनमें से कोई गैर-खाली उपसमुच्चय शून्य तक जोड़ता है? इस प्रकार यह निर्णय समस्या है और एनपी-पूर्ण होती है। एनपी-हार्ड समस्या का और उदाहरण भारित ग्राफ के सभी नोड्स के माध्यम से कम से कम निवेश वाले चक्रीय मार्ग को खोजने की अनुकूलन समस्या है। इसे सामान्यतः ट्रैवलिंग सेल्समैन की समस्या के रूप में जाना जाता है।[7] इस प्रकार ऐसी निर्णय समस्याएं हैं जो एनपी-हार्ड हैं किन्तु एनपी-पूर्ण नहीं हैं जैसे कि यही वह समस्या है जो प्रोग्राम और उसके इनपुट के बारे में पूछती है, क्या यह सदैव के लिए चलेगा? यह हां/नहीं प्रश्न है और इसलिए निर्णय समस्या है। यह साबित करना सरल है कि रुकने की समस्या एनपी-कठिन है किन्तु एनपी-पूर्ण नहीं है। उदाहरण के लिए, बूलियन संतुष्टि की समस्या को ट्यूरिंग मशीन के विवरण में बदलकर हॉल्टिंग समस्या में कम किया जा सकता है जो सभी सत्य मान असाइनमेंट की प्रयास करती है और इस प्रकार जब उसे कोई ऐसा मिल जाता है जो सूत्र को संतुष्ट करता है तो वह रुक जाता है और अन्यथा यह अनंत लूप में चला जाता है। यह देखना भी सरल है कि रुकने की समस्या एनपी में नहीं है क्योंकि एनपी में सभी समस्याएं संचालन की सीमित संख्या में निर्णायक होती हैं, किन्तु सामान्यतः रुकने की समस्या अनिर्णीत समस्या है। ऐसी एनपी-हार्ड समस्याएं भी हैं जो न तो एनपी-पूर्ण हैं और न ही अनिर्णीत हैं। उदाहरण के लिए, सही परिमाणित बूलियन सूत्र की भाषा पीएसपीएसीई में निर्णायक है, किन्तु गैर-नियतात्मक बहुपद समय में नहीं (जब तक कि एनपी = पीएसपीएसीई)।[8]
एनपी-नामकरण सम्मेलन
एनपी-कठिन समस्याओं को सम्मिश्र वर्ग एनपी का तत्व नहीं होना चाहिए। चूंकि एनपी कम्प्यूटेशनल सम्मिश्र सिद्धांत में केंद्रीय भूमिका निभाता है, इसे कई वर्गों के आधार के रूप में प्रयोग किया जाता है: एनपी (सम्मिश्र): कम्प्यूटेशनल निर्णय समस्याओं का वर्ग जिसके लिए किसी दिए गए सही-समाधान को बहुपद समय में नियतात्मक ट्यूरिंग मशीन (या बहुपद समय में गैर-नियतात्मक ट्यूरिंग मशीन द्वारा हल करने योग्य) द्वारा समाधान के रूप में सत्यापित किया जा सकता है। इस प्रकार एनपी-हार्ड: समस्याओं का वर्ग जो कम से कम एनपी में सबसे कठिन समस्याओं के रूप में कठिन हैं। समस्याएँ जो एनपी-हार्ड हैं उन्हें एनपी के तत्व होने की आवश्यकता नहीं है; वास्तव में, वे निर्णायक भी नहीं हो सकते हैं। इस प्रकार एनपी-पूर्ण: निर्णय समस्याओं का वर्ग जिसमें एनपी में सबसे कठिन समस्याएं हैं। प्रत्येक एनपी-पूर्ण समस्या को एनपी में होना चाहिए।
- एनपी-सरल
- एनपी जितना कठिन है, किन्तु एनपी में आवश्यक नहीं है।
एनपी-समतुल्य: निर्णय समस्याएं जो एनपी-हार्ड और एनपी-सरल दोनों हैं, किन्तु आवश्यक नहीं कि एनपी में होंटी है। इस प्रकार एनपी-इंटरमीडिएट: यदि P और एनपी अलग हैं, जिससे एनपी के क्षेत्र में निर्णय की समस्याएं उपस्थित हैं जो P और एनपी-पूर्ण समस्याओं के बीच आती हैं। (यदि P और एनपी ही वर्ग हैं, तो एनपी-मध्यवर्ती समस्याएं उपस्थित नहीं हैं क्योंकि इस स्थिति में प्रत्येक एनपी-पूर्ण समस्या P में आती है, और परिभाषा के अनुसार, एनपी में प्रत्येक समस्या को एनपी-पूर्ण समस्या में घटाया जा सकता है। )
आवेदन क्षेत्र
एनपी-हार्ड समस्याओं को अधिकांशतः नियम-आधारित भाषाओं से निपटाया जाता है जिनमें निम्न सम्मिलित हैं:
- अनुमानित कंप्यूटिंग
- विन्यास प्रबंधन
- क्रिप्टोग्राफी
- डेटा माइनिंग
- निर्णय समर्थन प्रणाली
- फाइलोजेनेटिक्स
- योजना
- प्रक्रिया निगरानी और नियंत्रण
- रोस्टर या शेड्यूल
- रूटिंग / वाहन रूटिंग
- अनुसूची
संदर्भ
- ↑ 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.
