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