एनपी पूर्णता: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| (7 intermediate revisions by 3 users not shown) | |||
| Line 3: | Line 3: | ||
# यह [[निर्णय समस्या]] है जिसका अर्थ है कि समस्या के किसी भी इनपुट के लिए, आउटपुट या तो हाँ या नहीं है। | # यह [[निर्णय समस्या]] है जिसका अर्थ है कि समस्या के किसी भी इनपुट के लिए, आउटपुट या तो हाँ या नहीं है। | ||
# जब उत्तर हां है तो इसे छोटी (बहुपद लंबाई) 'समाधान' के अस्तित्व के माध्यम से प्रदर्शित किया जा सकता है। | # जब उत्तर हां है तो इसे छोटी (बहुपद लंबाई) 'समाधान' के अस्तित्व के माध्यम से प्रदर्शित किया जा सकता है। | ||
# प्रत्येक समाधान की शुद्धता को जल्दी से सत्यापित किया जा सकता है (अर्थात् बहुपद समय में) और [[क्रूर-बल खोज]] एल्गोरिदम सभी संभावित समाधानों का प्रयास करके समाधान खोज | # प्रत्येक समाधान की शुद्धता को जल्दी से सत्यापित किया जा सकता है (अर्थात् बहुपद समय में) और [[क्रूर-बल खोज]] एल्गोरिदम सभी संभावित समाधानों का प्रयास करके समाधान खोज सकता है। | ||
# समस्या का उपयोग हर दूसरी समस्या का अनुकरण करने के लिए किया जा सकता है जिसके लिए हम जल्दी से सत्यापित कर सकते हैं कि समाधान सही है। इस अर्थ में एनपी-पूर्ण समस्याएँ उन समस्याओं में सबसे कठिन हैं जिनके समाधानों को शीघ्रता से सत्यापित किया जा सकता है। यदि हम कुछ एनपी-पूर्ण समस्या का समाधान जल्दी से पा सकते हैं तो हम जल्दी से हर दूसरी समस्या का समाधान खोज सकते हैं जिसके लिए दिए गए समाधान को आसानी से सत्यापित किया जा सकता है। | # समस्या का उपयोग हर दूसरी समस्या का अनुकरण करने के लिए किया जा सकता है जिसके लिए हम जल्दी से सत्यापित कर सकते हैं कि समाधान सही है। इस अर्थ में एनपी-पूर्ण समस्याएँ उन समस्याओं में सबसे कठिन हैं जिनके समाधानों को शीघ्रता से सत्यापित किया जा सकता है। यदि हम कुछ एनपी-पूर्ण समस्या का समाधान जल्दी से पा सकते हैं तो हम जल्दी से हर दूसरी समस्या का समाधान खोज सकते हैं जिसके लिए दिए गए समाधान को आसानी से सत्यापित किया जा सकता है। | ||
एनपी-पूर्ण नाम गैर-नियतात्मक बहुपद-समय पूर्ण के लिए छोटा है। इस नाम में [[गैर-नियतात्मक ट्यूरिंग मशीन]] को संदर्भित करता है जो ब्रूट-बल खोज एल्गोरिदम के विचार को गणितीय रूप से औपचारिक रूप देने का विधि है। बहुपद समय उस समय की मात्रा को संदर्भित करता है जिसे समाधान की जांच करने के लिए [[नियतात्मक एल्गोरिथ्म]] के लिए त्वरित माना जाता है या संपूर्ण खोज करने के लिए गैर-नियतात्मक ट्यूरिंग मशीन के लिए [[पूर्ण (जटिलता)]] ही [[जटिलता वर्ग]] में सब कुछ अनुकरण करने में सक्षम होने की संपत्ति को संदर्भित करता है। | एनपी-पूर्ण नाम गैर-नियतात्मक बहुपद-समय पूर्ण के लिए छोटा है। इस नाम में [[गैर-नियतात्मक ट्यूरिंग मशीन]] को संदर्भित करता है जो ब्रूट-बल खोज एल्गोरिदम के विचार को गणितीय रूप से औपचारिक रूप देने का विधि है। बहुपद समय उस समय की मात्रा को संदर्भित करता है जिसे समाधान की जांच करने के लिए [[नियतात्मक एल्गोरिथ्म]] के लिए त्वरित माना जाता है या संपूर्ण खोज करने के लिए गैर-नियतात्मक ट्यूरिंग मशीन के लिए [[पूर्ण (जटिलता)]] ही [[जटिलता वर्ग]] में सब कुछ अनुकरण करने में सक्षम होने की संपत्ति को संदर्भित करता है। | ||
अधिक स्पष्ट | अधिक स्पष्ट रूप से समस्या का प्रत्येक इनपुट बहुपद लंबाई के समाधान के सेट से जुड़ा होना चाहिए जिसकी वैधता का शीघ्रता से परीक्षण किया जा सकता है (बहुपद समय में)<ref>{{Cite book| last=Cobham | first=Alan | author-link=Alan Cobham | year = 1965 | chapter = The intrinsic computational difficulty of functions | title = प्रक्रिया। तर्कशास्त्र, कार्यप्रणाली और विज्ञान का दर्शन II| publisher = North Holland}}</ref> इस तरह कि किसी भी इनपुट के लिए आउटपुट हाँ है यदि समाधान सेट खाली नहीं है और नहीं तो यह खाली है। इस रूप की समस्याओं की जटिलता वर्ग को [[एनपी (जटिलता)]] कहा जाता है जो गैर-नियतात्मक बहुपद समय के लिए संक्षिप्त नाम है। समस्या को [[ एनपी कठिन |एनपी हार्ड]] कहा जाता है यदि एनपी में सब कुछ बहुपद समय में परिवर्तित हो सकता है तथापि वह एनपी में न हो इसके विपरीत समस्या एनपी-पूर्ण है यदि यह एनपी और एनपी-हार्ड दोनों में है। एनपी-पूर्ण समस्याएं एनपी में सबसे कठिन समस्याओं का प्रतिनिधित्व करती हैं। यदि कुछ एनपी-पूर्ण समस्या में बहुपद समय एल्गोरिदम होता है तो एनपी में सभी समस्याएं होती हैं। एनपी-पूर्ण समस्याओं का सेट अधिकांशतः एनपी-सी या एनपीसी द्वारा निरूपित किया जाता है। | ||
चूँकि एनपी-पूर्ण समस्या का समाधान शीघ्रता से ''सत्यापित'' किया जा सकता है किंतु समाधान को शीघ्रता से ''खोज ने'' का कोई ज्ञात विधि नहीं है। अर्थात् किसी भी वर्तमान में ज्ञात [[ कलन विधि |कलन विधि]] का उपयोग करके समस्या को हल करने के लिए आवश्यक समय तेजी से बढ़ता है क्योंकि समस्या का आकार बढ़ता है। परिणाम स्वरुप | चूँकि एनपी-पूर्ण समस्या का समाधान शीघ्रता से ''सत्यापित'' किया जा सकता है किंतु समाधान को शीघ्रता से ''खोज ने'' का कोई ज्ञात विधि नहीं है। अर्थात् किसी भी वर्तमान में ज्ञात [[ कलन विधि |कलन विधि]] का उपयोग करके समस्या को हल करने के लिए आवश्यक समय तेजी से बढ़ता है क्योंकि समस्या का आकार बढ़ता है। परिणाम स्वरुप यह निर्धारित करना कि क्या इन समस्याओं को जल्दी से हल करना संभव है जिसे [[पी बनाम एनपी समस्या]] कहा जाता है आज कंप्यूटर विज्ञान में विवर्त समस्याओं की मौलिक सूची में से है। | ||
जबकि एनपी-पूर्ण समस्याओं के समाधान की गणना करने का विधि जल्दी से अनदेखा रहता है कंप्यूटर वैज्ञानिक और [[कंप्यूटर प्रोग्राम]]र अभी भी अधिकांशतः एनपी-पूर्ण समस्याओं का सामना करते हैं। एनपी-पूर्ण समस्याओं को अधिकांशतः ह्यूरिस्टिक (कंप्यूटर विज्ञान) विधियों और सन्निकटन एल्गोरिदम का उपयोग करके संबोधित किया जाता है। | जबकि एनपी-पूर्ण समस्याओं के समाधान की गणना करने का विधि जल्दी से अनदेखा रहता है कंप्यूटर वैज्ञानिक और [[कंप्यूटर प्रोग्राम]]र अभी भी अधिकांशतः एनपी-पूर्ण समस्याओं का सामना करते हैं। एनपी-पूर्ण समस्याओं को अधिकांशतः ह्यूरिस्टिक (कंप्यूटर विज्ञान) विधियों और सन्निकटन एल्गोरिदम का उपयोग करके संबोधित किया जाता है। | ||
| Line 33: | Line 33: | ||
== पृष्ठभूमि == | == पृष्ठभूमि == | ||
[[File:P np np-complete np-hard.svg|thumb|300px|right|[[पी (जटिलता)]], एनपी (जटिलता), एनपी-पूर्ण, और एनपी-हार्ड समस्याओं के सेट के लिए [[यूलर आरेख]]। बायां पक्ष इस धारणा के तहत मान्य है कि पी बनाम एनपी समस्या | पी ≠ एनपी, जबकि दायां पक्ष इस धारणा के तहत मान्य है कि पी = एनपी (सिवाय इसके कि खाली भाषा और इसके पूरक कभी भी एनपी-पूर्ण नहीं होते हैं, और सामान्य तौर पर, पी या एनपी में हर समस्या एनपी-पूर्ण नहीं है)]]एनपी-पूर्णता की अवधारणा को 1971 में प्रस्तुत किया गया था (कुक-लेविन प्रमेय देखें) चूँकि एनपी-पूर्ण शब्द बाद में प्रस्तुत किया गया था। कम्प्यूटिंग सम्मेलन के सिद्धांत पर 1971 की संगोष्ठी में कंप्यूटर वैज्ञानिकों के बीच इस बात को लेकर | [[File:P np np-complete np-hard.svg|thumb|300px|right|[[पी (जटिलता)]], एनपी (जटिलता), एनपी-पूर्ण, और एनपी-हार्ड समस्याओं के सेट के लिए [[यूलर आरेख]]। बायां पक्ष इस धारणा के तहत मान्य है कि पी बनाम एनपी समस्या | पी ≠ एनपी, जबकि दायां पक्ष इस धारणा के तहत मान्य है कि पी = एनपी (सिवाय इसके कि खाली भाषा और इसके पूरक कभी भी एनपी-पूर्ण नहीं होते हैं, और सामान्य तौर पर, पी या एनपी में हर समस्या एनपी-पूर्ण नहीं है)]]एनपी-पूर्णता की अवधारणा को 1971 में प्रस्तुत किया गया था (कुक-लेविन प्रमेय देखें) चूँकि एनपी-पूर्ण शब्द बाद में प्रस्तुत किया गया था। कम्प्यूटिंग सम्मेलन के सिद्धांत पर 1971 की संगोष्ठी में कंप्यूटर वैज्ञानिकों के बीच इस बात को लेकर कटु बहस हुई कि क्या [[नियतात्मक]] [[ट्यूरिंग मशीन]] पर एनपी-पूर्ण समस्याओं को बहुपद समय में हल किया जा सकता है। [[जॉन हॉपक्रॉफ्ट]] ने सम्मेलन में सभी को आम सहमति के लिए लाया कि क्या एनपी-पूर्ण समस्याएं बहुपद समय में हल करने योग्य हैं या नहीं कुछ बाद की तारीख में हल करने के लिए बंद कर दिया जाना चाहिए क्योंकि किसी के पास उनके प्रमाणित के लिए कोई औपचारिक प्रमाण नहीं था या दूसरा . इसे P=NP के प्रश्न के रूप में जाना जाता है। | ||
कोई भी अभी तक निर्णायक रूप से यह निर्धारित करने में सक्षम नहीं है कि क्या एनपी-पूर्ण समस्याएं वास्तव में बहुपद समय में हल करने योग्य हैं यह गणित की महान अनसुलझी समस्याओं में से है। [[ मिट्टी गणित संस्थान |मिट्टी गणित संस्थान]] किसी को भी $1 मिलियन का इनाम दे रहा है जिसके पास P=NP या P≠NP का औपचारिक प्रमाण है।<ref>{{Cite web |last=Kiersz |first=Andy |title=An eminent mathematician claims to have solved one of math's greatest mysteries — and it's one of 6 problems with a $1 million prize |url=https://www.businessinsider.com/millennium-prize-problems-million-dollar-prize-2017-12 |access-date=2023-04-24 |website=Business Insider |language=en-US}}</ref> | कोई भी अभी तक निर्णायक रूप से यह निर्धारित करने में सक्षम नहीं है कि क्या एनपी-पूर्ण समस्याएं वास्तव में बहुपद समय में हल करने योग्य हैं यह गणित की महान अनसुलझी समस्याओं में से है। [[ मिट्टी गणित संस्थान |मिट्टी गणित संस्थान]] किसी को भी $1 मिलियन का इनाम दे रहा है जिसके पास P=NP या P≠NP का औपचारिक प्रमाण है।<ref>{{Cite web |last=Kiersz |first=Andy |title=An eminent mathematician claims to have solved one of math's greatest mysteries — and it's one of 6 problems with a $1 million prize |url=https://www.businessinsider.com/millennium-prize-problems-million-dollar-prize-2017-12 |access-date=2023-04-24 |website=Business Insider |language=en-US}}</ref> | ||
एनपी-पूर्ण समस्याओं का अस्तित्व स्पष्ट नहीं है। कुक-लेविन प्रमेय कहता है कि बूलियन संतुष्टि समस्या एनपी-पूर्ण है इस प्रकार यह स्थापित करता है कि ऐसी समस्याएं उपस्थित हैं। 1972 में [[रिचर्ड कार्प]] ने सिद्ध किया कि कई अन्य समस्याएं भी एनपी-पूर्ण थीं (कार्प की 21 एनपी-पूर्ण समस्याएं देखें) इस प्रकार एनपी-पूर्ण समस्याओं का वर्ग है (बूलियन संतुष्टि समस्या के अतिरिक्त )। मूल परिणामों के बाद से हजारों अन्य समस्याओं को एनपी-पूर्ण दिखाया गया है, अन्य समस्याओं को पहले एनपी-पूर्ण दिखाया गया है; इनमें से कई समस्याओं को [[माइकल गैरी]] और डेविड एस. जॉनसन | एनपी-पूर्ण समस्याओं का अस्तित्व स्पष्ट नहीं है। कुक-लेविन प्रमेय कहता है कि बूलियन संतुष्टि समस्या एनपी-पूर्ण है इस प्रकार यह स्थापित करता है कि ऐसी समस्याएं उपस्थित हैं। 1972 में [[रिचर्ड कार्प]] ने सिद्ध किया कि कई अन्य समस्याएं भी एनपी-पूर्ण थीं (कार्प की 21 एनपी-पूर्ण समस्याएं देखें) इस प्रकार एनपी-पूर्ण समस्याओं का वर्ग है (बूलियन संतुष्टि समस्या के अतिरिक्त )। मूल परिणामों के बाद से हजारों अन्य समस्याओं को एनपी-पूर्ण दिखाया गया है, अन्य समस्याओं को पहले एनपी-पूर्ण दिखाया गया है; इनमें से कई समस्याओं को [[माइकल गैरी]] और डेविड एस. जॉनसन की 1979 की पुस्तक कंप्यूटर्स एंड इंट्रेक्टेबिलिटी: ए गाइड टू द थ्योरी ऑफ एनपी-कम्प्लीटनेस में संकलित किया गया है।<ref name="GareyJohnson">{{cite book |last1=Garey |first1=Michael R. |author-link1=Michael R. Garey |last2=Johnson |first2=D. S. |author-link2=David S. Johnson |title=Computers and Intractability: A Guide to the Theory of NP-Completeness |year=1979 |isbn=978-0-7167-1045-5 |pages=[https://archive.org/details/computersintract0000gare/page/ x+338] |series=A Series of Books in the Mathematical Sciences |editor=Victor Klee |editor-link=Victor Klee |publisher=W. H. Freeman and Co. |location=San Francisco, Calif. |mr=519066 |title-link=Computers and Intractability: A Guide to the Theory of NP-Completeness }}</ref> | ||
| Line 62: | Line 62: | ||
दाईं ओर कुछ समस्याओं का आरेख है और कमी (जटिलता) सामान्यतः उनकी एनपी-पूर्णता सिद्ध करने के लिए उपयोग की जाती है। इस डायग्राम में समस्याओं को नीचे से ऊपर की ओर कम किया गया है। ध्यान दें कि यह आरेख इन समस्याओं के बीच गणितीय संबंध के विवरण के रूप में भ्रामक है क्योंकि किसी भी दो एनपी-पूर्ण समस्याओं के बीच [[बहुपद-समय में कमी]] उपस्थित है किंतु यह इंगित करता है कि इस बहुपद-समय में कमी को प्रदर्शित करना सबसे आसान कहां रहा है। | दाईं ओर कुछ समस्याओं का आरेख है और कमी (जटिलता) सामान्यतः उनकी एनपी-पूर्णता सिद्ध करने के लिए उपयोग की जाती है। इस डायग्राम में समस्याओं को नीचे से ऊपर की ओर कम किया गया है। ध्यान दें कि यह आरेख इन समस्याओं के बीच गणितीय संबंध के विवरण के रूप में भ्रामक है क्योंकि किसी भी दो एनपी-पूर्ण समस्याओं के बीच [[बहुपद-समय में कमी]] उपस्थित है किंतु यह इंगित करता है कि इस बहुपद-समय में कमी को प्रदर्शित करना सबसे आसान कहां रहा है। | ||
पी और एनपी-पूर्ण समस्या में समस्या के बीच अधिकांशतः केवल छोटा सा अंतर होता है। उदाहरण के लिए 3-संतोषजनक समस्या बूलियन संतुष्टि समस्या का प्रतिबंध एनपी-पूर्ण रहता है जबकि थोड़ा अधिक प्रतिबंधित 2-संतोषजनक समस्या पी में है (विशेष रूप से यह [[एनएल-पूर्ण]] है) किंतु थोड़ा अधिक सामान्य अधिकतम . 2-शनि. समस्या फिर से एनपी-पूर्ण है। यह निर्धारित करना कि ग्राफ़ को 2 रंगों से रंगा जा सकता है या नहीं, P में है, किंतु 3 रंगों के साथ NP-पूर्ण है तथापि | पी और एनपी-पूर्ण समस्या में समस्या के बीच अधिकांशतः केवल छोटा सा अंतर होता है। उदाहरण के लिए 3-संतोषजनक समस्या बूलियन संतुष्टि समस्या का प्रतिबंध एनपी-पूर्ण रहता है जबकि थोड़ा अधिक प्रतिबंधित 2-संतोषजनक समस्या पी में है (विशेष रूप से यह [[एनएल-पूर्ण]] है) किंतु थोड़ा अधिक सामान्य अधिकतम . 2-शनि. समस्या फिर से एनपी-पूर्ण है। यह निर्धारित करना कि ग्राफ़ को 2 रंगों से रंगा जा सकता है या नहीं, P में है, किंतु 3 रंगों के साथ NP-पूर्ण है तथापि वह समतलीय ग्राफ़ तक सीमित हो। यह निर्धारित करना कि कोई ग्राफ़ [[चक्र ग्राफ]] है या द्विदलीय ग्राफ़ बहुत आसान है ([[एल (जटिलता)]] में) किंतु अधिकतम द्विदलीय या अधिकतम चक्र सबग्राफ खोजना एनपी-पूर्ण है। इष्टतम समाधान के किसी भी निश्चित प्रतिशत के अंदर नैपसैक समस्या का समाधान बहुपद समय में गणना किया जा सकता है किंतु इष्टतम समाधान खोजना एनपी-पूर्ण है। | ||
=== इंटरमीडिएट समस्याएं === | === इंटरमीडिएट समस्याएं === | ||
| Line 70: | Line 70: | ||
*सबग्राफ तुल्याकारिता: क्या ग्राफ़ G<sub>1</sub> ग्राफ़ G<sub>2</sub> के सबग्राफ़ के तुल्याकार है? | *सबग्राफ तुल्याकारिता: क्या ग्राफ़ G<sub>1</sub> ग्राफ़ G<sub>2</sub> के सबग्राफ़ के तुल्याकार है? | ||
सबग्राफ समरूपता समस्या एनपी-पूर्ण है। ग्राफ समरूपता समस्या न तो पी और न ही एनपी-पूर्ण होने का संदेह है चूँकि यह एनपी में है। यह ऐसी समस्या का उदाहरण है जिसे कठिन माना जाता है किंतु एनपी-पूर्ण नहीं माना जाता है। इस वर्ग को एनपी-इंटरमीडिएट समस्याएं कहा जाता है और उपस्थित है यदि और केवल यदि | सबग्राफ समरूपता समस्या एनपी-पूर्ण है। ग्राफ समरूपता समस्या न तो पी और न ही एनपी-पूर्ण होने का संदेह है चूँकि यह एनपी में है। यह ऐसी समस्या का उदाहरण है जिसे कठिन माना जाता है किंतु एनपी-पूर्ण नहीं माना जाता है। इस वर्ग को एनपी-इंटरमीडिएट समस्याएं कहा जाता है और उपस्थित है यदि और केवल यदि P≠NP। | ||
== एनपी-पूर्ण समस्याओं का समाधान == | == एनपी-पूर्ण समस्याओं का समाधान == | ||
| Line 76: | Line 76: | ||
सामान्य रूप से कम्प्यूटेशनल समस्याओं को हल करने के लिए निम्नलिखित विधियों को प्रयुक्त किया जा सकता है और वे अधिकांशतः अधिक तेज एल्गोरिदम को जन्म देते हैं: | सामान्य रूप से कम्प्यूटेशनल समस्याओं को हल करने के लिए निम्नलिखित विधियों को प्रयुक्त किया जा सकता है और वे अधिकांशतः अधिक तेज एल्गोरिदम को जन्म देते हैं: | ||
* [[जेनेटिक एल्गोरिद्म]]: इष्टतम समाधान खोजने के अतिरिक्त | * [[जेनेटिक एल्गोरिद्म]]: इष्टतम समाधान खोजने के अतिरिक्त ऐसे समाधान की खोज करें जो इष्टतम से अधिक से अधिक कारक हो। | ||
* [[ यादृच्छिक एल्गोरिदम ]]: तेजी से चलने वाले औसत समय को प्राप्त करने के लिए रैंडमनेस का उपयोग करें और एल्गोरिथ्म को कुछ छोटी संभावना के साथ विफल होने दें। नोट[[मोंटे कार्लो विधि]] पद्धति इस विशिष्ट अर्थ में कुशल एल्गोरिथम का उदाहरण नहीं है चूँकि आनुवंशिक एल्गोरिदम जैसे विकासवादी दृष्टिकोण हो सकते हैं। | * [[ यादृच्छिक एल्गोरिदम ]]: तेजी से चलने वाले औसत समय को प्राप्त करने के लिए रैंडमनेस का उपयोग करें और एल्गोरिथ्म को कुछ छोटी संभावना के साथ विफल होने दें। नोट[[मोंटे कार्लो विधि]] पद्धति इस विशिष्ट अर्थ में कुशल एल्गोरिथम का उदाहरण नहीं है चूँकि आनुवंशिक एल्गोरिदम जैसे विकासवादी दृष्टिकोण हो सकते हैं। | ||
* प्रतिबंध: इनपुट की संरचना को प्रतिबंधित करके (उदाहरण के लिए प्लानर ग्राफ़ के लिए) तेज़ एल्गोरिदम सामान्यतः संभव होते हैं। | * प्रतिबंध: इनपुट की संरचना को प्रतिबंधित करके (उदाहरण के लिए प्लानर ग्राफ़ के लिए) तेज़ एल्गोरिदम सामान्यतः संभव होते हैं। | ||
| Line 82: | Line 82: | ||
* ह्यूरिस्टिक (कंप्यूटर विज्ञान): एल्गोरिथ्म जो कई स्थिति में यथोचित रूप से अच्छी तरह से काम करता है किंतु इसके लिए कोई प्रमाण नहीं है कि यह सदैव तेज़ होता है और सदैव अच्छा परिणाम देता है। [[मेटाह्यूरिस्टिक]] दृष्टिकोण अधिकांशतः उपयोग किए जाते हैं। | * ह्यूरिस्टिक (कंप्यूटर विज्ञान): एल्गोरिथ्म जो कई स्थिति में यथोचित रूप से अच्छी तरह से काम करता है किंतु इसके लिए कोई प्रमाण नहीं है कि यह सदैव तेज़ होता है और सदैव अच्छा परिणाम देता है। [[मेटाह्यूरिस्टिक]] दृष्टिकोण अधिकांशतः उपयोग किए जाते हैं। | ||
हेयुरिस्टिक एल्गोरिथम का एक उदाहरण एक सबऑप्टिमल <math>O(n\log n)</math> लालची कलरिंग एल्गोरिथम है जिसका उपयोग कुछ कंपाइलरों के रजिस्टर आवंटन चरण के समय ग्राफ़ कलरिंग के लिए किया जाता है, एक विधि | हेयुरिस्टिक एल्गोरिथम का एक उदाहरण एक सबऑप्टिमल <math>O(n\log n)</math> लालची कलरिंग एल्गोरिथम है जिसका उपयोग कुछ कंपाइलरों के रजिस्टर आवंटन चरण के समय ग्राफ़ कलरिंग के लिए किया जाता है, एक विधि जिसे ग्राफ़-कलरिंग ग्लोबल रजिस्टर एलोकेशन कहा जाता है। प्रत्येक शीर्ष एक चर है किनारों को उन चरों के बीच खींचा जाता है जो एक ही समय में उपयोग किए जा रहे हैं और रंग प्रत्येक चर को निर्दिष्ट रजिस्टर को इंगित करते हैं। चूंकि अधिकांश आरआईएससी मशीनों में अधिक बड़ी संख्या में सामान्य-उद्देश्य रजिस्टर होते हैं यहां तक कि एक अनुमानी दृष्टिकोण भी इस आवेदन के लिए प्रभावी है। | ||
== विभिन्न प्रकार की कमी के तहत पूर्णता == | == विभिन्न प्रकार की कमी के तहत पूर्णता == | ||
| Line 89: | Line 89: | ||
एक अन्य प्रकार की कमी बहुपद-समय ट्यूरिंग कमी है। एक समस्या <math>\scriptstyle X</math> एक समस्या के लिए बहुपद-समय ट्यूरिंग-कम करने योग्य है <math>\scriptstyle Y</math> यदि एक सबरूटीन दिया गया है जो <math>\scriptstyle Y</math> को बहुपद समय में हल करता है तो कोई एक प्रोग्राम लिख सकता है जो इस सबरूटीन को कॉल करता है और बहुपद समय में <math>\scriptstyle X</math> को हल करता है। यह कई-एक रिड्यूसबिलिटी के विपरीत है जिसमें प्रतिबंध है कि प्रोग्राम केवल एक बार सबरूटीन को कॉल कर सकता है और सबरूटीन का रिटर्न वैल्यू प्रोग्राम का रिटर्न वैल्यू होना चाहिए। | एक अन्य प्रकार की कमी बहुपद-समय ट्यूरिंग कमी है। एक समस्या <math>\scriptstyle X</math> एक समस्या के लिए बहुपद-समय ट्यूरिंग-कम करने योग्य है <math>\scriptstyle Y</math> यदि एक सबरूटीन दिया गया है जो <math>\scriptstyle Y</math> को बहुपद समय में हल करता है तो कोई एक प्रोग्राम लिख सकता है जो इस सबरूटीन को कॉल करता है और बहुपद समय में <math>\scriptstyle X</math> को हल करता है। यह कई-एक रिड्यूसबिलिटी के विपरीत है जिसमें प्रतिबंध है कि प्रोग्राम केवल एक बार सबरूटीन को कॉल कर सकता है और सबरूटीन का रिटर्न वैल्यू प्रोग्राम का रिटर्न वैल्यू होना चाहिए। | ||
यदि कोई एनालॉग को कई-एक कमी के अतिरिक्त | यदि कोई एनालॉग को कई-एक कमी के अतिरिक्त ट्यूरिंग कमी के साथ एन[[पी-पूर्ण]] के रूप में परिभाषित करता है तो समस्याओं का परिणामी सेट एनपी-पूर्ण से छोटा नहीं होगा; यह विवर्त प्रश्न है कि क्या यह कोई बड़ा होगा। | ||
एक अन्य प्रकार की कमी जिसका उपयोग अधिकांशतः एनपी-पूर्णता को परिभाषित करने के लिए किया जाता है वह है लॉगरिदमिक-स्पेस मल्टी-वन कमी जो कि कई-वन कमी है जिसे केवल स्पेस के लॉगरिदमिक राशि के साथ गणना की जा सकती है। चूंकि [[लघुगणकीय स्थान]] में की जा सकने वाली हर गणना बहुपद समय में भी की जा सकती है इसलिए यह इस प्रकार है कि यदि कोई लॉगरिदमिक-स्पेस मल्टी-वन कमी है तो बहुपद-टाइम मल्टी-वन कमी भी है। इस प्रकार की कमी अधिक सामान्य बहुपद-समय कई-एक कमी से अधिक परिष्कृत है और यह हमें पी-पूर्ण जैसे अधिक वर्गों को अलग करने की अनुमति देती है। क्या इस प्रकार की कमी के तहत एनपी-पूर्ण परिवर्तन की परिभाषा अभी भी एक खुली समस्या है। वर्तमान में ज्ञात सभी एनपी-पूर्ण समस्याएं लॉग स्पेस कमी के तहत एनपी-पूर्ण हैं। <math>AC_0</math>कमी और <math>NC_0</math> कमी जैसी अशक्त कमी के तहत भी वर्तमान में ज्ञात सभी एनपी-कंप्लीट समस्या एनपी-कंप्लीट रहती है। कुछ एनपी-पूर्ण समस्याएं जैसे कि एसएटी बहुलगणकीय समय अनुमानों के तहत भी पूर्ण होने के लिए जाना जाता है।<ref>{{Cite journal | doi=10.1006/jcss.1998.1583 | last1=Agrawal | first1=M. | author1-link=Manindra Agrawal | last2=Allender | first2=E. | last3=Rudich | first3=Steven | author3-link=Steven Rudich | title=Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem | year=1998 | journal=Journal of Computer and System Sciences | issn=1090-2724 | volume=57 | issue=2 | pages=127–143 | doi-access=free }}</ref> चूँकि यह ज्ञात है कि एसीओ कमी बहुपद-समय की कमी से सख्ती से छोटी कक्षा को परिभाषित करती है।<ref>{{Cite journal | last1=Agrawal | first1=M. | author1-link=Manindra Agrawal | last2=Allender | first2=E. | last3=Impagliazzo | first3=R. | last4=Pitassi | first4=T. | author4-link = Toniann Pitassi | last5=Rudich | first5=Steven | author5-link=Steven Rudich | title=कटौती की जटिलता को कम करना| doi=10.1007/s00037-001-8191-1 | year=2001 | journal=Computational Complexity | issn=1016-3328 | volume=10 | pages=117–138 | issue=2 | s2cid=29017219 }} | एक अन्य प्रकार की कमी जिसका उपयोग अधिकांशतः एनपी-पूर्णता को परिभाषित करने के लिए किया जाता है वह है लॉगरिदमिक-स्पेस मल्टी-वन कमी जो कि कई-वन कमी है जिसे केवल स्पेस के लॉगरिदमिक राशि के साथ गणना की जा सकती है। चूंकि [[लघुगणकीय स्थान]] में की जा सकने वाली हर गणना बहुपद समय में भी की जा सकती है इसलिए यह इस प्रकार है कि यदि कोई लॉगरिदमिक-स्पेस मल्टी-वन कमी है तो बहुपद-टाइम मल्टी-वन कमी भी है। इस प्रकार की कमी अधिक सामान्य बहुपद-समय कई-एक कमी से अधिक परिष्कृत है और यह हमें पी-पूर्ण जैसे अधिक वर्गों को अलग करने की अनुमति देती है। क्या इस प्रकार की कमी के तहत एनपी-पूर्ण परिवर्तन की परिभाषा अभी भी एक खुली समस्या है। वर्तमान में ज्ञात सभी एनपी-पूर्ण समस्याएं लॉग स्पेस कमी के तहत एनपी-पूर्ण हैं। <math>AC_0</math>कमी और <math>NC_0</math> कमी जैसी अशक्त कमी के तहत भी वर्तमान में ज्ञात सभी एनपी-कंप्लीट समस्या एनपी-कंप्लीट रहती है। कुछ एनपी-पूर्ण समस्याएं जैसे कि एसएटी बहुलगणकीय समय अनुमानों के तहत भी पूर्ण होने के लिए जाना जाता है।<ref>{{Cite journal | doi=10.1006/jcss.1998.1583 | last1=Agrawal | first1=M. | author1-link=Manindra Agrawal | last2=Allender | first2=E. | last3=Rudich | first3=Steven | author3-link=Steven Rudich | title=Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem | year=1998 | journal=Journal of Computer and System Sciences | issn=1090-2724 | volume=57 | issue=2 | pages=127–143 | doi-access=free }}</ref> चूँकि यह ज्ञात है कि एसीओ कमी बहुपद-समय की कमी से सख्ती से छोटी कक्षा को परिभाषित करती है।<ref>{{Cite journal | last1=Agrawal | first1=M. | author1-link=Manindra Agrawal | last2=Allender | first2=E. | last3=Impagliazzo | first3=R. | last4=Pitassi | first4=T. | author4-link = Toniann Pitassi | last5=Rudich | first5=Steven | author5-link=Steven Rudich | title=कटौती की जटिलता को कम करना| doi=10.1007/s00037-001-8191-1 | year=2001 | journal=Computational Complexity | issn=1016-3328 | volume=10 | pages=117–138 | issue=2 | s2cid=29017219 }} | ||
| Line 119: | Line 119: | ||
* यदि पी = एनपी, सभी क्रिप्टोग्राफ़िक सिफर को तोड़ा जा सकता है। यदि बहुपद की डिग्री या स्थिरांक अधिक बड़े हैं तो बहुपद-समय की समस्या को व्यवहार में हल करना बहुत कठिन हो सकता है। इसके अतिरिक्त [[सूचना-सैद्धांतिक सुरक्षा]] क्रिप्टोग्राफ़िक विधि प्रदान करती है जिसे असीमित कंप्यूटिंग शक्ति के साथ भी नहीं तोड़ा जा सकता है। | * यदि पी = एनपी, सभी क्रिप्टोग्राफ़िक सिफर को तोड़ा जा सकता है। यदि बहुपद की डिग्री या स्थिरांक अधिक बड़े हैं तो बहुपद-समय की समस्या को व्यवहार में हल करना बहुत कठिन हो सकता है। इसके अतिरिक्त [[सूचना-सैद्धांतिक सुरक्षा]] क्रिप्टोग्राफ़िक विधि प्रदान करती है जिसे असीमित कंप्यूटिंग शक्ति के साथ भी नहीं तोड़ा जा सकता है। | ||
* एक बड़े मापदंड पर क्वांटम कंप्यूटर एनपी-पूर्ण समस्याओं को कुशलतापूर्वक हल करने में सक्षम होगा। निर्णय समस्याओं का वर्ग जिसे दोष-सहिष्णु क्वांटम कंप्यूटर द्वारा कुशलतापूर्वक (सिद्धांत रूप में) हल किया जा सकता है बीक्यूपी के रूप में जाना जाता है। चूँकि बीक्यूपी में सभी एनपी सम्मिलित नहीं माना जाता है और यदि ऐसा नहीं होता है तो इसमें कोई एनपी-पूर्ण समस्या नहीं हो सकती है।<ref>{{cite conference | last = Aaronson | first = Scott | editor-last = Schulman | editor-first = Leonard J. | contribution = BQP and the polynomial hierarchy | doi = 10.1145/1806689.1806711 | pages = 141–150 | publisher = Association for Computing Machinery | title = Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5–8 June 2010 | year = 2010}}</ref> | * एक बड़े मापदंड पर क्वांटम कंप्यूटर एनपी-पूर्ण समस्याओं को कुशलतापूर्वक हल करने में सक्षम होगा। निर्णय समस्याओं का वर्ग जिसे दोष-सहिष्णु क्वांटम कंप्यूटर द्वारा कुशलतापूर्वक (सिद्धांत रूप में) हल किया जा सकता है बीक्यूपी के रूप में जाना जाता है। चूँकि बीक्यूपी में सभी एनपी सम्मिलित नहीं माना जाता है और यदि ऐसा नहीं होता है तो इसमें कोई एनपी-पूर्ण समस्या नहीं हो सकती है।<ref>{{cite conference | last = Aaronson | first = Scott | editor-last = Schulman | editor-first = Leonard J. | contribution = BQP and the polynomial hierarchy | doi = 10.1145/1806689.1806711 | pages = 141–150 | publisher = Association for Computing Machinery | title = Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5–8 June 2010 | year = 2010}}</ref> | ||
== गुण == | |||
== गुण == | |||
एक निर्णय समस्या को देखते हुए या कुछ निश्चित एन्कोडिंग में औपचारिक भाषा के रूप में परिभाषा सभी एनपी-पूर्ण समस्याओं का सेट एनपीसी इसके तहत बंद नहीं है: | एक निर्णय समस्या को देखते हुए या कुछ निश्चित एन्कोडिंग में औपचारिक भाषा के रूप में परिभाषा सभी एनपी-पूर्ण समस्याओं का सेट एनपीसी इसके तहत बंद नहीं है: | ||
* [[संघ (सेट सिद्धांत)]] | * [[संघ (सेट सिद्धांत)]] | ||
* [[चौराहा]] | * [[चौराहा|प्रतिच्छेदन]] | ||
* जोड़ | * जोड़ | ||
* [[क्लेन स्टार]] | * [[क्लेन स्टार]] | ||
| Line 307: | Line 305: | ||
{{ComplexityClasses}} | {{ComplexityClasses}} | ||
{{DEFAULTSORT:Np-Complete}} | {{DEFAULTSORT:Np-Complete}} | ||
[[Category: | [[Category:All Wikipedia articles needing clarification|Np-Complete]] | ||
[[Category:Created On 15/05/2023]] | [[Category:Articles with hatnote templates targeting a nonexistent page|Np-Complete]] | ||
[[Category:CS1 English-language sources (en)]] | |||
[[Category:Collapse templates|Np-Complete]] | |||
[[Category:Created On 15/05/2023|Np-Complete]] | |||
[[Category:Lua-based templates|Np-Complete]] | |||
[[Category:Machine Translated Page|Np-Complete]] | |||
[[Category:Multi-column templates|Np-Complete]] | |||
[[Category:Navigational boxes| ]] | |||
[[Category:Navigational boxes without horizontal lists|Np-Complete]] | |||
[[Category:Pages using div col with small parameter|Np-Complete]] | |||
[[Category:Pages with script errors|Np-Complete]] | |||
[[Category:Sidebars with styles needing conversion|Np-Complete]] | |||
[[Category:Template documentation pages|Documentation/doc]] | |||
[[Category:Templates Vigyan Ready|Np-Complete]] | |||
[[Category:Templates generating microformats|Np-Complete]] | |||
[[Category:Templates that add a tracking category|Np-Complete]] | |||
[[Category:Templates that are not mobile friendly|Np-Complete]] | |||
[[Category:Templates that generate short descriptions|Np-Complete]] | |||
[[Category:Templates using TemplateData|Np-Complete]] | |||
[[Category:Templates using under-protected Lua modules|Np-Complete]] | |||
[[Category:Webarchive template wayback links]] | |||
[[Category:Wikipedia articles needing clarification from July 2021|Np-Complete]] | |||
[[Category:Wikipedia fully protected templates|Div col]] | |||
[[Category:Wikipedia metatemplates|Np-Complete]] | |||
[[Category:एनपी-पूर्ण समस्याएं| एनपी-पूर्ण समस्याएं ]] | |||
[[Category:कंप्यूटिंग में 1971|Np-Complete]] | |||
[[Category:गणितीय अनुकूलन|Np-Complete]] | |||
[[Category:जटिलता वर्ग|Np-Complete]] | |||
Latest revision as of 14:54, 12 June 2023
File:3SAT 17 svg.svg
बूलियन संतुष्टि की समस्या (एसएटी) यह निर्धारित करने के लिए कहती है कि क्या तर्कवाक्य सूत्र (उदाहरण दर्शाया गया है) को उसके चरों के लिए सत्य मानों के उपयुक्त असाइनमेंट (समाधान) द्वारा सत्य बनाया जा सकता है। चूँकि यह सत्यापित करना आसान है कि दिया गया असाइनमेंट सूत्र को सही बनाता है या नहीं,[1] संतोषजनक असाइनमेंट खोजने के लिए अनिवार्य रूप से कोई तेज़ विधि नहीं जाना जाता है, जो सभी असाइनमेंट को लगातार करने की कोशिश करता है। स्टीफन कुक और लियोनिद लेविन ने सिद्ध किया कि प्रत्येक आसान-से-सत्यापित समस्या को एसएटी के रूप में तेजी से हल किया जा सकता है, जो कि एनपी-पूर्ण है।
कम्प्यूटेशनल जटिलता सिद्धांत में समस्या एनपी-पूर्ण होती है जब:
- यह निर्णय समस्या है जिसका अर्थ है कि समस्या के किसी भी इनपुट के लिए, आउटपुट या तो हाँ या नहीं है।
- जब उत्तर हां है तो इसे छोटी (बहुपद लंबाई) 'समाधान' के अस्तित्व के माध्यम से प्रदर्शित किया जा सकता है।
- प्रत्येक समाधान की शुद्धता को जल्दी से सत्यापित किया जा सकता है (अर्थात् बहुपद समय में) और क्रूर-बल खोज एल्गोरिदम सभी संभावित समाधानों का प्रयास करके समाधान खोज सकता है।
- समस्या का उपयोग हर दूसरी समस्या का अनुकरण करने के लिए किया जा सकता है जिसके लिए हम जल्दी से सत्यापित कर सकते हैं कि समाधान सही है। इस अर्थ में एनपी-पूर्ण समस्याएँ उन समस्याओं में सबसे कठिन हैं जिनके समाधानों को शीघ्रता से सत्यापित किया जा सकता है। यदि हम कुछ एनपी-पूर्ण समस्या का समाधान जल्दी से पा सकते हैं तो हम जल्दी से हर दूसरी समस्या का समाधान खोज सकते हैं जिसके लिए दिए गए समाधान को आसानी से सत्यापित किया जा सकता है।
एनपी-पूर्ण नाम गैर-नियतात्मक बहुपद-समय पूर्ण के लिए छोटा है। इस नाम में गैर-नियतात्मक ट्यूरिंग मशीन को संदर्भित करता है जो ब्रूट-बल खोज एल्गोरिदम के विचार को गणितीय रूप से औपचारिक रूप देने का विधि है। बहुपद समय उस समय की मात्रा को संदर्भित करता है जिसे समाधान की जांच करने के लिए नियतात्मक एल्गोरिथ्म के लिए त्वरित माना जाता है या संपूर्ण खोज करने के लिए गैर-नियतात्मक ट्यूरिंग मशीन के लिए पूर्ण (जटिलता) ही जटिलता वर्ग में सब कुछ अनुकरण करने में सक्षम होने की संपत्ति को संदर्भित करता है।
अधिक स्पष्ट रूप से समस्या का प्रत्येक इनपुट बहुपद लंबाई के समाधान के सेट से जुड़ा होना चाहिए जिसकी वैधता का शीघ्रता से परीक्षण किया जा सकता है (बहुपद समय में)[2] इस तरह कि किसी भी इनपुट के लिए आउटपुट हाँ है यदि समाधान सेट खाली नहीं है और नहीं तो यह खाली है। इस रूप की समस्याओं की जटिलता वर्ग को एनपी (जटिलता) कहा जाता है जो गैर-नियतात्मक बहुपद समय के लिए संक्षिप्त नाम है। समस्या को एनपी हार्ड कहा जाता है यदि एनपी में सब कुछ बहुपद समय में परिवर्तित हो सकता है तथापि वह एनपी में न हो इसके विपरीत समस्या एनपी-पूर्ण है यदि यह एनपी और एनपी-हार्ड दोनों में है। एनपी-पूर्ण समस्याएं एनपी में सबसे कठिन समस्याओं का प्रतिनिधित्व करती हैं। यदि कुछ एनपी-पूर्ण समस्या में बहुपद समय एल्गोरिदम होता है तो एनपी में सभी समस्याएं होती हैं। एनपी-पूर्ण समस्याओं का सेट अधिकांशतः एनपी-सी या एनपीसी द्वारा निरूपित किया जाता है।
चूँकि एनपी-पूर्ण समस्या का समाधान शीघ्रता से सत्यापित किया जा सकता है किंतु समाधान को शीघ्रता से खोज ने का कोई ज्ञात विधि नहीं है। अर्थात् किसी भी वर्तमान में ज्ञात कलन विधि का उपयोग करके समस्या को हल करने के लिए आवश्यक समय तेजी से बढ़ता है क्योंकि समस्या का आकार बढ़ता है। परिणाम स्वरुप यह निर्धारित करना कि क्या इन समस्याओं को जल्दी से हल करना संभव है जिसे पी बनाम एनपी समस्या कहा जाता है आज कंप्यूटर विज्ञान में विवर्त समस्याओं की मौलिक सूची में से है।
जबकि एनपी-पूर्ण समस्याओं के समाधान की गणना करने का विधि जल्दी से अनदेखा रहता है कंप्यूटर वैज्ञानिक और