एनपी-कठोरता: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{short description|Complexity class}} | {{short description|Complexity class}} | ||
{{for| | {{for|एक विनम्र परिचय|पी बनाम एनपी समस्या}} | ||
[[File:P np np-complete np-hard.svg|alt=Euler diagram for P, NP, NP-पूर्ण, और समस्याओं का एनपी-हार्ड सेट। थंब|[[पी (जटिलता)]], [[एनपी (जटिलता)]], एनपी-पूर्ण, और एनपी-हार्ड समस्याओं का सेट के लिए 300 पीएक्स। बायां पक्ष इस धारणा के तहत मान्य है कि पी बनाम एनपी समस्या | पी ≠ एनपी, जबकि दायां पक्ष इस धारणा के तहत मान्य है कि पी = एनपी (सिवाय इसके कि खाली भाषा और इसके पूरक कभी भी एनपी-पूर्ण नहीं होते हैं)]][[कम्प्यूटेशनल जटिलता सिद्धांत]] में, | [[File:P np np-complete np-hard.svg|alt=Euler diagram for P, NP, NP-पूर्ण, और समस्याओं का एनपी-हार्ड सेट। थंब|[[पी (जटिलता)]], [[एनपी (जटिलता)]], एनपी-पूर्ण, और एनपी-हार्ड समस्याओं का सेट के लिए 300 पीएक्स। बायां पक्ष इस धारणा के तहत मान्य है कि पी बनाम एनपी समस्या | पी ≠ एनपी, जबकि दायां पक्ष इस धारणा के तहत मान्य है कि पी = एनपी (सिवाय इसके कि खाली भाषा और इसके पूरक कभी भी एनपी-पूर्ण नहीं होते हैं)]] | ||
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, NP-कठोरता (NP (जटिलता) या गैर-नियतात्मक बहुपद-समय की कठोरता) समस्याओं के वर्ग की परिभाषित संपत्ति है जो अनौपचारिक रूप से कम से कम NP (जटिलता) में सबसे कठिन समस्याओं के रूप में कठिन हैं। NP-हार्ड समस्या का सरल उदाहरण [[सबसेट योग समस्या|उपसमुच्चय योग समस्या]] है। | |||
एक अधिक स्पष्ट विनिर्देश है: समस्या 'H' NP-हार्ड है जब NP में हर समस्या 'L' बहुपद समय में '''H''<nowiki/>' में [[कमी (जटिलता)]] हो सकती है; अर्थात्, ''H'' के लिए हल मानकर 1 इकाई समय लगता है, ''H''{{'}}बहुपद समय में L को हल करने के लिए s समाधान का उपयोग किया जा सकता है।<ref name="Leeuwen">{{cite book |editor1-first=Jan van |editor1-last=Leeuwen |editor1-link=Jan van Leeuwen |year=1998 |title=Handbook of Theoretical Computer Science |volume=A, Algorithms and complexity |location=Amsterdam |publisher=Elsevier |isbn=0262720140 |oclc=247934368}}</ref><ref>{{cite journal|last1=Knuth|first1=Donald|title=Postscript about NP-hard problems|journal=ACM SIGACT News|date=1974|volume=6|issue=2|pages=15–16|doi=10.1145/1008304.1008305|s2cid=46480926}}</ref> इस प्रकार परिणाम , किसी भी NP-हार्ड समस्या को हल करने के लिए बहुपद समय एल्गोरिदम खोजना NP में सभी समस्याओं के लिए बहुपद समय एल्गोरिदम प्रदान करता है। जैसा कि संदेह है कि P बनाम NP या P≠NP, यह संभावना नहीं है कि ऐसा एल्गोरिदम उपस्थित है।<ref>{{cite book|author1 = Daniel Pierre Bovet | author2 = Pierluigi Crescenzi | title = Introduction to the Theory of Complexity | publisher = Prentice Hall | page = 69 | isbn=0-13-915380-2| year = 1994 }}</ref> | |||
यह संदेह है कि NP-हार्ड समस्याओं के लिए कोई बहुपद-समय एल्गोरिदम नहीं हैं, किन्तु यह सिद्ध नहीं हुआ है।<ref>{{Cite web|url=http://www.scottaaronson.com/blog/?p=1720|title=Shtetl-Optimized » Blog Archive » The Scientific Case for P≠NP|website=www.scottaaronson.com|access-date=2016-09-25}}</ref> इस प्रकार इसके अतिरिक्त, कक्षा P (जटिलता), जिसमें बहुपद समय में सभी समस्याओं को हल किया जा सकता है, NP (जटिलता) वर्ग में निहित है।<ref>{{Cite web|url=http://www.scottaaronson.com/democritus/lec6.html|title=PHYS771 Lecture 6: P, NP, and Friends|website=www.scottaaronson.com|access-date=2016-09-25}}</ref> | |||
== परिभाषा == | == परिभाषा == | ||
एक [[निर्णय समस्या]] | एक [[निर्णय समस्या]] H NP-हार्ड है जब NP में हर समस्या L के लिए, बहुत-एक कमी है | बहुपद-समय कई-एक कमी L से H तक होते है।<ref name="Leeuwen"/>{{rp|80}} एक समतुल्य परिभाषा की आवश्यकता है कि NP में हर समस्या L को बहुपद समय में [[ओरेकल मशीन]] द्वारा H के लिए ओरेकल के साथ हल किया जा सकता है।<ref>{{cite book | author=V. J. Rayward-Smith | title= A First Course in Computability | year=1986 | isbn = 0-632-01307-9 | publisher=Blackwell | page = 159 }}</ref> अनौपचारिक रूप से, एल्गोरिथ्म के बारे में सोचा जा सकता है जो H को हल करने के लिए ऐसी ऑरेकल मशीन को सबरूटीन के रूप में कॉल करता है और L को बहुपद समय में हल करता है यदि सबरूटीन कॉल गणना करने के लिए केवल कदम लेता है। | ||
एक समतुल्य परिभाषा की आवश्यकता है कि | |||
एक और परिभाषा की आवश्यकता है कि | एक और परिभाषा की आवश्यकता है कि NP-पूर्ण समस्या जी से H तक बहुपद-समय की कमी होटी है।<ref name="Leeuwen"/>{{rp|91}} चूंकि NP में कोई समस्या L बहुपद समय में जी को कम कर देता है, इस प्रकार L बदले में बहुपद समय में H को कम कर देता है, इसलिए यह नई परिभाषा पिछले का तात्पर्य है। यह वर्ग NP-हार्ड को निर्णय समस्याओं तक सीमित नहीं करता है, और इसमें [[खोज समस्या]]एं या [[अनुकूलन समस्या]]एं भी सम्मिलित हैं। | ||
== परिणाम == | == परिणाम == | ||
यदि | यदि P ≠ NP, तो NP-हार्ड समस्याओं को बहुपद समय में हल नहीं किया जा सकता था। | ||
कुछ | कुछ NP-हार्ड ऑप्टिमाइज़ेशन समस्याएं कुछ स्थिर सन्निकटन अनुपात (विशेष रूप से, [[एपीएक्स]] में) या यहां तक कि किसी भी सन्निकटन अनुपात (बहुपद-समय सन्निकटन योजना में जटिलता वर्ग या बहुपद के रूप में) तक बहुपद-समय [[सन्निकटन एल्गोरिथ्म]] हो सकती हैं। समय सन्निकटन योजना नियतात्मक)। | ||
== उदाहरण == | == उदाहरण == | ||
NP-हार्ड समस्या का उदाहरण निर्णय उपसमुच्चय योग समस्या है: पूर्णांकों का सेट दिया गया है, क्या उनमें से कोई गैर-खाली उपसमुच्चय शून्य तक जोड़ता है? इस प्रकार यह निर्णय समस्या है और NP-पूर्ण होती है। NP-हार्ड समस्या का और उदाहरण भारित ग्राफ के सभी नोड्स के माध्यम से कम से कम निवेश वाले चक्रीय मार्ग को खोजने की अनुकूलन समस्या है। इसे सामान्यतः [[ट्रैवलिंग सेल्समैन की समस्या]] के रूप में जाना जाता है।<ref>{{citation|first1=E. L.|last1=Lawler|author1-link=Eugene Lawler|first2=J. K.|last2=Lenstra|author2-link=Jan Karel Lenstra|first3=A. H. G.|last3=Rinnooy Kan|first4=D. B.|last4=Shmoys|title=The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization|year=1985|publisher=John Wiley & Sons|isbn=0-471-90413-9|url-access=registration|url=https://archive.org/details/travelingsalesma00lawl}}.</ref> इस प्रकार ऐसी निर्णय समस्याएं हैं जो NP-हार्ड हैं किन्तु NP-पूर्ण नहीं हैं जैसे कि यही वह समस्या है जो प्रोग्राम और उसके इनपुट के बारे में पूछती है, क्या यह सदैव के लिए चलेगा? यह हां/नहीं प्रश्न है और इसलिए निर्णय समस्या है। यह साबित करना सरल है कि रुकने की समस्या NP-कठिन है किन्तु NP-पूर्ण नहीं है। उदाहरण के लिए, बूलियन संतुष्टि की समस्या को [[ट्यूरिंग मशीन]] के विवरण में बदलकर हॉल्टिंग समस्या में कम किया जा सकता है जो सभी सत्य मान असाइनमेंट की प्रयास करती है और इस प्रकार जब उसे कोई ऐसा मिल जाता है जो सूत्र को संतुष्ट करता है तो वह रुक जाता है और अन्यथा यह अनंत लूप में चला जाता है। यह देखना भी सरल है कि रुकने की समस्या NP में नहीं है क्योंकि NP में सभी समस्याएं संचालन की सीमित संख्या में निर्णायक होती हैं, किन्तु सामान्यतः रुकने की समस्या [[अनिर्णीत समस्या]] है। ऐसी NP-हार्ड समस्याएं भी हैं जो न तो NP-पूर्ण हैं और न ही अनिर्णीत हैं। उदाहरण के लिए, [[सही परिमाणित बूलियन सूत्र]] की भाषा [[पीएसपीएसीई]] में निर्णायक है, किन्तु गैर-नियतात्मक बहुपद समय में नहीं (जब तक कि NP = पीएसपीएसीई)।<ref>More precisely, this language is [[PSPACE-complete]]; see, for example, {{citation|title=Complexity Theory: Exploring the Limits of Efficient Algorithms|first=Ingo|last=Wegener|publisher=Springer|year=2005|isbn=9783540210450|page=189|url=https://books.google.com/books?id=1fo7_KoFUPsC&pg=PA189}}.</ref> | |||
ऐसी निर्णय समस्याएं हैं जो | |||
== | == 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-हार्ड समस्याओं को अधिकांशतः नियम-आधारित भाषाओं से निपटाया जाता है जिनमें निम्न सम्मिलित हैं: | |||
* अनुमानित कंप्यूटिंग | * अनुमानित कंप्यूटिंग | ||
* [[विन्यास प्रबंधन]] | * [[विन्यास प्रबंधन]] | ||
* [[क्रिप्टोग्राफी]] | * [[क्रिप्टोग्राफी]] | ||
* [[डेटा खनन]] | * [[डेटा खनन|डेटा माइनिंग]] | ||
* [[निर्णय समर्थन प्रणाली]] | * [[निर्णय समर्थन प्रणाली]] | ||
* [[फाइलोजेनेटिक्स]] | * [[फाइलोजेनेटिक्स]] | ||
Revision as of 11:35, 15 July 2023
कम्प्यूटेशनल जटिलता सिद्धांत में, 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.
