एनपी पूर्णता

बूलियन संतुष्टि की समस्या (एसएटी) यह निर्धारित करने के लिए कहती है कि क्या एक तर्कवाक्य सूत्र (उदाहरण दर्शाया गया है) को उसके चरों के लिए सत्य मानों के उपयुक्त असाइनमेंट (समाधान) द्वारा सत्य बनाया जा सकता है। हालांकि यह सत्यापित करना आसान है कि दिया गया असाइनमेंट सूत्र को सही बनाता है या नहीं, एक संतोषजनक असाइनमेंट खोजने के लिए अनिवार्य रूप से कोई तेज़ तरीका नहीं जाना जाता है, जो सभी असाइनमेंट को लगातार करने की कोशिश करता है। स्टीफन कुक और लियोनिद लेविन ने साबित किया कि प्रत्येक आसान-से-सत्यापित समस्या को एसएटी के रूप में तेजी से हल किया जा सकता है, जो कि एनपी-पूर्ण है।

कम्प्यूटेशनल जटिलता सिद्धांत में, एक समस्या एनपी-पूर्ण होती है जब:

1. यह एक निर्णय समस्या है, जिसका अर्थ है कि समस्या के किसी भी इनपुट के लिए, आउटपुट या तो हाँ या नहीं है।
2. जब उत्तर हां है, तो इसे एक छोटी (बहुपद लंबाई) 'समाधान' के अस्तित्व के माध्यम से प्रदर्शित किया जा सकता है।
3. प्रत्येक समाधान की शुद्धता को जल्दी से सत्यापित किया जा सकता है (अर्थात्, बहुपद समय में) और एक क्रूर-बल खोज एल्गोरिदम सभी संभावित समाधानों का प्रयास करके समाधान ढूंढ सकता है।
4. समस्या का उपयोग हर दूसरी समस्या का अनुकरण करने के लिए किया जा सकता है जिसके लिए हम जल्दी से सत्यापित कर सकते हैं कि समाधान सही है। इस अर्थ में, एनपी-पूर्ण समस्याएँ उन समस्याओं में सबसे कठिन हैं जिनके समाधानों को शीघ्रता से सत्यापित किया जा सकता है। अगर हम कुछ एनपी-पूर्ण समस्या का समाधान जल्दी से पा सकते हैं, तो हम जल्दी से हर दूसरी समस्या का समाधान खोज सकते हैं, जिसके लिए दिए गए समाधान को आसानी से सत्यापित किया जा सकता है।

एनपी-पूर्ण नाम गैर-नियतात्मक बहुपद-समय पूर्ण के लिए छोटा है। इस नाम में, गैर-नियतात्मक ट्यूरिंग मशीनों को संदर्भित करता है, जो एक जानवर-बल खोज एल्गोरिदम के विचार को गणितीय रूप से औपचारिक रूप देने का एक तरीका है। बहुपद समय उस समय की मात्रा को संदर्भित करता है जिसे एक समाधान की जांच करने के लिए एक नियतात्मक एल्गोरिथ्म के लिए त्वरित माना जाता है, या संपूर्ण खोज करने के लिए एक गैर-नियतात्मक ट्यूरिंग मशीन के लिए। पूर्ण (जटिलता) एक ही जटिलता वर्ग में सब कुछ अनुकरण करने में सक्षम होने की संपत्ति को संदर्भित करता है।

अधिक सटीक रूप से, समस्या का प्रत्येक इनपुट बहुपद लंबाई के समाधान के एक सेट से जुड़ा होना चाहिए, जिसकी वैधता का शीघ्रता से परीक्षण किया जा सकता है (बहुपद समय में), इस तरह कि किसी भी इनपुट के लिए आउटपुट हाँ है यदि समाधान सेट खाली नहीं है और नहीं तो यह खाली है। इस रूप की समस्याओं की जटिलता वर्ग को एनपी (जटिलता) कहा जाता है, जो गैर-नियतात्मक बहुपद समय के लिए एक संक्षिप्त नाम है। एक समस्या को एनपी कठिन कहा जाता है अगर एनपी में सब कुछ बहुपद समय में परिवर्तित हो सकता है, भले ही वह एनपी में न हो। इसके विपरीत, एक समस्या एनपी-पूर्ण है यदि यह एनपी और एनपी-हार्ड दोनों में है। एनपी-पूर्ण समस्याएं एनपी में सबसे कठिन समस्याओं का प्रतिनिधित्व करती हैं। अगर कुछ एनपी-पूर्ण समस्या में बहुपद समय एल्गोरिदम होता है, तो एनपी में सभी समस्याएं होती हैं। एनपी-पूर्ण समस्याओं का सेट अक्सर एनपी-सी या एनपीसी द्वारा निरूपित किया जाता है।

हालांकि एनपी-पूर्ण समस्या का समाधान शीघ्रता से सत्यापित किया जा सकता है, लेकिन समाधान को शीघ्रता से ढूंढने का कोई ज्ञात तरीका नहीं है। अर्थात्, किसी भी वर्तमान में ज्ञात कलन विधि का उपयोग करके समस्या को हल करने के लिए आवश्यक समय तेजी से बढ़ता है क्योंकि समस्या का आकार बढ़ता है। नतीजतन, यह निर्धारित करना कि क्या इन समस्याओं को जल्दी से हल करना संभव है, जिसे पी बनाम एनपी समस्या कहा जाता है, आज कंप्यूटर विज्ञान में खुली समस्याओं की मौलिक सूची में से एक है।

जबकि एनपी-पूर्ण समस्याओं के समाधान की गणना करने का एक तरीका जल्दी से अनदेखा रहता है, कंप्यूटर वैज्ञानिक और कंप्यूटर प्रोग्रामर अभी भी अक्सर एनपी-पूर्ण समस्याओं का सामना करते हैं। एनपी-पूर्ण समस्याओं को अक्सर ह्यूरिस्टिक (कंप्यूटर विज्ञान) विधियों और सन्निकटन एल्गोरिदम का उपयोग करके संबोधित किया जाता है।

सिंहावलोकन

एनपी-पूर्ण समस्याएं एनपी (जटिलता) में हैं, सभी निर्णय समस्याओं का सेट जिनके समाधान बहुपद समय में सत्यापित किए जा सकते हैं; एनपी को समान रूप से निर्णय समस्याओं के सेट के रूप में परिभाषित किया जा सकता है जिसे गैर-नियतात्मक ट्यूरिंग मशीन पर बहुपद समय में हल किया जा सकता है। एनपी में एक समस्या पी एनपी-पूर्ण है अगर एनपी में हर दूसरी समस्या बहुपद समय में पी में परिवर्तित (या कम) हो सकती है।

यह ज्ञात नहीं है कि एनपी में हर समस्या को जल्दी से हल किया जा सकता है या नहीं - इसे पी बनाम एनपी समस्या कहा जाता है। लेकिन अगर किसी एनपी-पूर्ण समस्या को जल्दी से हल किया जा सकता है, तो एनपी में हर समस्या हो सकती है, क्योंकि एनपी-पूर्ण समस्या की परिभाषा बताती है कि एनपी में हर समस्या को हर एनपी-पूर्ण समस्या के लिए शीघ्रता से कम किया जाना चाहिए (अर्थात, यह कर सकते हैं) बहुपद समय में घटाया जा सकता है)। इस वजह से, अक्सर यह कहा जाता है कि एनपी-पूर्ण समस्याएं सामान्य रूप से एनपी समस्याओं से कठिन या अधिक कठिन होती हैं।

औपचारिक परिभाषा

See also: formal definition for NP-completeness (article P = NP)

एक निर्णय समस्या $\scriptstyle C$ एनपी-पूर्ण है अगर:

1. $\scriptstyle C$ एनपी में है, और
2. एनपी में हर समस्या कई-एक कमी है $\scriptstyle C$ बहुपद समय में।

$\scriptstyle C$ एनपी में यह प्रदर्शित करके दिखाया जा सकता है कि एक उम्मीदवार समाधान $\scriptstyle C$ बहुपद समय में सत्यापित किया जा सकता है।

ध्यान दें कि स्थिति 2 को संतुष्ट करने वाली समस्या को एनपी-हार्ड कहा जाता है, चाहे वह स्थिति 1 को संतुष्ट करती हो या नहीं। इस परिभाषा का एक परिणाम यह है कि यदि हमारे पास एक बहुपद समय एल्गोरिथ्म था (एक यूनिवर्सल ट्यूरिंग मशीन पर, या किसी अन्य ट्यूरिंग पूर्णता | ट्यूरिंग-समतुल्य सार मशीन) के लिए $\scriptstyle C$, हम एनपी में सभी समस्याओं को बहुपद समय में हल कर सकते हैं।

पृष्ठभूमि

पी ≠ एनपी, जबकि दायां पक्ष इस धारणा के तहत मान्य है कि पी = एनपी (सिवाय इसके कि खाली भाषा और इसके पूरक कभी भी एनपी-पूर्ण नहीं होते हैं, और सामान्य तौर पर, पी या एनपी में हर समस्या एनपी-पूर्ण नहीं है)

एनपी-पूर्णता की अवधारणा को 1971 में पेश किया गया था (कुक-लेविन प्रमेय देखें), हालांकि एनपी-पूर्ण शब्द बाद में पेश किया गया था। कम्प्यूटिंग सम्मेलन के सिद्धांत पर 1971 की संगोष्ठी में, कंप्यूटर वैज्ञानिकों के बीच इस बात को लेकर तीखी बहस हुई कि क्या नियतात्मक ट्यूरिंग मशीन पर एनपी-पूर्ण समस्याओं को बहुपद समय में हल किया जा सकता है। जॉन हॉपक्रॉफ्ट ने सम्मेलन में सभी को एक आम सहमति के लिए लाया कि क्या एनपी-पूर्ण समस्याएं बहुपद समय में हल करने योग्य हैं या नहीं, कुछ बाद की तारीख में हल करने के लिए बंद कर दिया जाना चाहिए, क्योंकि किसी के पास उनके दावों के लिए कोई औपचारिक सबूत नहीं था या दूसरा . इसे P=NP के प्रश्न के रूप में जाना जाता है।

कोई भी अभी तक निर्णायक रूप से यह निर्धारित करने में सक्षम नहीं है कि क्या एनपी-पूर्ण समस्याएं वास्तव में बहुपद समय में हल करने योग्य हैं, यह गणित की महान अनसुलझी समस्याओं में से एक है। मिट्टी गणित संस्थान किसी को भी $1 मिलियन का इनाम दे रहा है, जिसके पास P=NP या P≠NP का औपचारिक प्रमाण है। एनपी-पूर्ण समस्याओं का अस्तित्व स्पष्ट नहीं है। कुक-लेविन प्रमेय कहता है कि बूलियन संतुष्टि समस्या एनपी-पूर्ण है, इस प्रकार यह स्थापित करता है कि ऐसी समस्याएं मौजूद हैं। 1972 में, रिचर्ड कार्प ने साबित किया कि कई अन्य समस्याएं भी एनपी-पूर्ण थीं (कार्प की 21 एनपी-पूर्ण समस्याएं देखें); इस प्रकार, एनपी-पूर्ण समस्याओं का एक वर्ग है (बूलियन संतुष्टि समस्या के अलावा)। मूल परिणामों के बाद से, हजारों अन्य समस्याओं को एनपी-पूर्ण दिखाया गया है, अन्य समस्याओं को पहले एनपी-पूर्ण दिखाया गया है; इनमें से कई समस्याओं को माइकल गैरी और डेविड एस. जॉनसन|जॉनसन की 1979 की पुस्तक कंप्यूटर्स एंड इंट्रेक्टेबिलिटी: ए गाइड टू द थ्योरी ऑफ एनपी-कम्प्लीटनेस में संकलित किया गया है।

एनपी-पूर्ण समस्याएं

कुछ एनपी-पूर्ण समस्याएं, कमी (जटिलता) का संकेत देते हुए आमतौर पर उनकी एनपी-पूर्णता साबित करने के लिए उपयोग की जाती हैं

Main article: List of NP-complete problems

यह साबित करने का सबसे आसान तरीका है कि कुछ नई समस्या एनपी-पूर्ण है, पहले यह साबित करना है कि यह एनपी में है, और फिर कुछ ज्ञात एनपी-पूर्ण समस्या को कम करना है। इसलिए, विभिन्न प्रकार की एनपी-पूर्ण समस्याओं को जानना उपयोगी है। नीचे दी गई सूची में कुछ प्रसिद्ध समस्याएं हैं जो निर्णय समस्याओं के रूप में व्यक्त किए जाने पर एनपी-पूर्ण हैं।

• बूलियन संतुष्टि समस्या | बूलियन संतुष्टि समस्या (SAT)
• बस्ता समस्या
• हैमिल्टनियन पथ समस्या
• ट्रैवलिंग सेल्समैन की समस्या (निर्णय संस्करण)
• सबग्राफ समरूपता समस्या
• उपसमुच्चय योग समस्या
• क्लिक समस्या
• वर्टेक्स कवर समस्या
• स्वतंत्र सेट समस्या
• हावी सेट समस्या
• ग्राफ रंग समस्या

दाईं ओर कुछ समस्याओं का आरेख है और कमी (जटिलता) आमतौर पर उनकी एनपी-पूर्णता साबित करने के लिए उपयोग की जाती है। इस डायग्राम में समस्याओं को नीचे से ऊपर की ओर कम किया गया है। ध्यान दें कि यह आरेख इन समस्याओं के बीच गणितीय संबंध के विवरण के रूप में भ्रामक है, क्योंकि किसी भी दो एनपी-पूर्ण समस्याओं के बीच बहुपद-समय में कमी मौजूद है; लेकिन यह इंगित करता है कि इस बहुपद-समय में कमी को प्रदर्शित करना सबसे आसान कहां रहा है।

पी और एनपी-पूर्ण समस्या में समस्या के बीच अक्सर केवल एक छोटा सा अंतर होता है। उदाहरण के लिए, 3-संतोषजनक समस्या, बूलियन संतुष्टि समस्या का प्रतिबंध, एनपी-पूर्ण रहता है, जबकि थोड़ा अधिक प्रतिबंधित 2-संतोषजनक समस्या पी में है (विशेष रूप से, यह एनएल-पूर्ण है), लेकिन थोड़ा अधिक सामान्य अधिकतम . 2-शनि. समस्या फिर से एनपी-पूर्ण है। यह निर्धारित करना कि ग्राफ़ को 2 रंगों से रंगा जा सकता है या नहीं, P में है, लेकिन 3 रंगों के साथ NP-पूर्ण है, भले ही वह समतलीय ग्राफ़ तक सीमित हो। यह निर्धारित करना कि कोई ग्राफ़ एक चक्र ग्राफ़ है या द्विदलीय ग्राफ़ बहुत आसान है (एल (जटिलता) में), लेकिन अधिकतम द्विदलीय या अधिकतम चक्र सबग्राफ खोजना एनपी-पूर्ण है। इष्टतम समाधान के किसी भी निश्चित प्रतिशत के भीतर नैपसैक समस्या का समाधान बहुपद समय में गणना किया जा सकता है, लेकिन इष्टतम समाधान खोजना एनपी-पूर्ण है।

इंटरमीडिएट समस्याएं

एक दिलचस्प उदाहरण ग्राफ समरूपता समस्या है, यह निर्धारित करने की ग्राफ सिद्धांत समस्या है कि दो ग्राफों के बीच एक ग्राफ समरूपता मौजूद है या नहीं। दो ग्राफ़ समरूपी हैं यदि एक को वर्टेक्स (ग्राफ़ सिद्धांत) का नाम बदलकर दूसरे में समाकृतिकता हो सकता है। इन दो समस्याओं पर विचार करें:

• ग्राफ समरूपता: क्या ग्राफ जी है₁ ग्राफ जी के लिए आइसोमोर्फिक₂?
• सबग्राफ समरूपता: क्या ग्राफ जी है₁ ग्राफ जी के एक सबग्राफ के लिए आइसोमोर्फिक₂?

सबग्राफ समरूपता समस्या एनपी-पूर्ण है। ग्राफ समरूपता समस्या न तो पी और न ही एनपी-पूर्ण होने का संदेह है, हालांकि यह एनपी में है। यह एक ऐसी समस्या का उदाहरण है जिसे कठिन माना जाता है, लेकिन एनपी-पूर्ण नहीं माना जाता है। इस वर्ग को एनपी-इंटरमीडिएट समस्याएं कहा जाता है और मौजूद है अगर और केवल अगर पी≠एनपी।

एनपी-पूर्ण समस्याओं का समाधान

वर्तमान में, एनपी-पूर्ण समस्याओं के लिए सभी ज्ञात एल्गोरिदम में समय की आवश्यकता होती है जो वास्तव में इनपुट आकार में अधिबहुपद है exponential in $O(n^{k})$ कुछ के लिए $k>0$ और यह अज्ञात है कि क्या कोई तेज़ एल्गोरिथम हैं।

सामान्य रूप से कम्प्यूटेशनल समस्याओं को हल करने के लिए निम्नलिखित तकनीकों को लागू किया जा सकता है, और वे अक्सर काफी तेज एल्गोरिदम को जन्म देते हैं:

• जेनेटिक एल्गोरिद्म: एक इष्टतम समाधान खोजने के बजाय, एक ऐसे समाधान की खोज करें जो एक इष्टतम से अधिक से अधिक एक कारक हो।
• यादृच्छिक एल्गोरिदम : तेजी से चलने वाले औसत समय को प्राप्त करने के लिए रैंडमनेस का उपयोग करें, और एल्गोरिथ्म को कुछ छोटी संभावना के साथ विफल होने दें। नोटमोंटे कार्लो विधि पद्धति इस विशिष्ट अर्थ में एक कुशल एल्गोरिथम का उदाहरण नहीं है, हालांकि आनुवंशिक एल्गोरिदम जैसे विकासवादी दृष्टिकोण हो सकते हैं।
• प्रतिबंध: इनपुट की संरचना को प्रतिबंधित करके (उदाहरण के लिए, प्लानर ग्राफ़ के लिए), तेज़ एल्गोरिदम आमतौर पर संभव होते हैं।
• पैरामीटरयुक्त जटिलता: यदि इनपुट के कुछ पैरामीटर निश्चित हैं तो अक्सर तेज़ एल्गोरिदम होते हैं।
• ह्यूरिस्टिक (कंप्यूटर विज्ञान): एक एल्गोरिथ्म जो कई मामलों में यथोचित रूप से अच्छी तरह से काम करता है, लेकिन इसके लिए कोई प्रमाण नहीं है कि यह हमेशा तेज़ होता है और हमेशा एक अच्छा परिणाम देता है। मेटाह्यूरिस्टिक दृष्टिकोण अक्सर उपयोग किए जाते हैं।

एक अनुमानी एल्गोरिथम का एक उदाहरण उपइष्टतम है $O(n\log n)$ लालची रंग कुछ कंपाइलरों के रजिस्टर आवंटन चरण के दौरान ग्राफ रंग की समस्या के लिए उपयोग किया जाता है, एक तकनीक जिसे ग्राफ-रंग वैश्विक रजिस्टर आवंटन कहा जाता है। प्रत्येक शीर्ष एक चर है, किनारों को उन चरों के बीच खींचा जाता है जो एक ही समय में उपयोग किए जा रहे हैं, और रंग प्रत्येक चर को निर्दिष्ट रजिस्टर को इंगित करते हैं। चूंकि अधिकांश जोखिम मशीनों में काफी बड़ी संख्या में सामान्य-उद्देश्य आवंटन रजिस्टर करें हैं, यहां तक ​​कि एक अनुमानी दृष्टिकोण भी इस आवेदन के लिए प्रभावी है।

विभिन्न प्रकार की कमी के तहत पूर्णता

ऊपर दी गई एनपी-पूर्ण की परिभाषा में, बहुपद-समय कई-एक कमी के तकनीकी अर्थ में कमी शब्द का उपयोग किया गया था।

एक अन्य प्रकार की कमी बहुपद-समय ट्यूरिंग कमी है। एक समस्या $\scriptstyle X$ एक समस्या के लिए बहुपद-समय ट्यूरिंग-कम करने योग्य है $\scriptstyle Y$ अगर, एक सबरूटीन दिया गया है जो हल करता है $\scriptstyle Y$ बहुपद समय में, कोई एक प्रोग्राम लिख सकता है जो इस सबरूटीन को कॉल करता है और हल करता है $\scriptstyle X$ बहुपद समय में। यह कई-एक रिड्यूसबिलिटी के विपरीत है, जिसमें प्रतिबंध है कि प्रोग्राम केवल एक बार सबरूटीन को कॉल कर सकता है, और सबरूटीन का रिटर्न वैल्यू प्रोग्राम का रिटर्न वैल्यू होना चाहिए।

यदि कोई एनालॉग को कई-एक कटौती के बजाय ट्यूरिंग कटौती के साथ एनपी-पूर्ण के रूप में परिभाषित करता है, तो समस्याओं का परिणामी सेट एनपी-पूर्ण से छोटा नहीं होगा; यह एक खुला प्रश्न है कि क्या यह कोई बड़ा होगा।

एक अन्य प्रकार की कमी जिसका उपयोग अक्सर एनपी-पूर्णता को परिभाषित करने के लिए किया जाता है, वह है लघुगणक-अंतरिक्ष अनेक-एक कमी जो कि कई-वन रिडक्शन है जिसे केवल स्पेस के लॉगरिदमिक राशि के साथ गणना की जा सकती है। चूंकि लघुगणकीय स्थान में की जा सकने वाली हर गणना बहुपद समय में भी की जा सकती है, इसलिए यह इस प्रकार है कि यदि कोई लॉगरिदमिक-स्पेस मल्टी-वन रिडक्शन है तो बहुपद-टाइम मल्टी-वन रिडक्शन भी है। इस प्रकार की कमी अधिक सामान्य बहुपद-समय कई-एक कटौती से अधिक परिष्कृत है और यह हमें पी-पूर्ण जैसे अधिक वर्गों को अलग करने की अनुमति देती है। क्या इस प्रकार की कटौती के तहत एनपी-पूर्ण परिवर्तन की परिभाषा अभी भी एक खुली समस्या है। वर्तमान में ज्ञात सभी एनपी-पूर्ण समस्याएं लॉग स्पेस कटौती के तहत एनपी-पूर्ण हैं। वर्तमान में ज्ञात सभी एनपी-पूर्ण समस्याएं बहुत कमजोर कटौती के तहत भी एनपी-पूर्ण बनी हुई हैं $AC_{0}$ कटौती और $NC_{0}$ कटौती। कुछ एनपी-पूर्ण समस्याएं जैसे कि एसएटी को पॉलीलॉगरिदमिक समय अनुमानों के तहत भी पूर्ण माना जाता है। हालाँकि, यह ज्ञात है कि AC0|AC⁰ कटौती बहुपद-समय कटौती की तुलना में सख्ती से छोटी कक्षा को परिभाषित करती है।

नामकरण

डोनाल्ड नुथ के अनुसार, एनपी-पूर्ण नाम को मैं अल्फ्रेड हूं , जॉन होपक्रॉफ्ट और जेफरी उल्मैन ने अपनी प्रसिद्ध पाठ्यपुस्तक द डिजाइन एंड एनालिसिस ऑफ कंप्यूटर एल्गोरिदम में लोकप्रिय बनाया था। वह रिपोर्ट करता है कि उन्होंने किताब के लिए गैली प्रूफ में बदलाव पेश किया (बहुपद-पूर्ण से), सैद्धांतिक कंप्यूटर विज्ञान समुदाय के एक सर्वेक्षण के परिणामों के अनुसार। पोल में किए गए अन्य सुझाव हरक्यूलिस के मजदूर, दुर्जेय, कुक के सम्मान में केनेथ स्टिग्लिट्ज़ की कड़ी मेहनत, और शेन लिन का संक्षिप्त नाम पीईटी शामिल है, जो शायद घातीय समय के लिए खड़ा था, लेकिन पी बनाम एनपी समस्या किस तरह से चली गई, इसके आधार पर इसका मतलब हो सकता हैprovably चरघातांकी समय या पूर्व चरघातांकी समय ।

आम गलतफहमी

निम्नलिखित गलत धारणाएं अक्सर होती हैं। * एनपी-पूर्ण समस्याएँ सबसे कठिन ज्ञात समस्याएँ हैं। चूंकि एनपी-पूर्ण समस्याएं एनपी में हैं, उनका चलने का समय सबसे अधिक घातीय है। हालाँकि, कुछ समस्याओं के लिए अधिक समय की आवश्यकता साबित हुई है, उदाहरण के लिए प्रेसबर्गर अंकगणित। कुछ समस्याओं में से, यह भी सिद्ध हो चुका है कि उन्हें कभी भी हल नहीं किया जा सकता है, उदाहरण के लिए रुकने की समस्या।

• एनपी-पूर्ण समस्याएँ कठिन हैं क्योंकि बहुत सारे अलग-अलग समाधान हैं। एक ओर, ऐसी कई समस्याएं हैं जिनका समाधान स्थान उतना ही बड़ा है, लेकिन बहुपद समय में हल किया जा सकता है (उदाहरण के लिए न्यूनतम फैले पेड़)। दूसरी ओर, अधिकांश एक समाधान के साथ एनपी-समस्याएं हैं जो यादृच्छिक बहुपद-समय में कमी के तहत एनपी-हार्ड हैं (देखें वैलेंट-वजीरानी प्रमेय)।
• एनपी-पूर्ण समस्याओं को हल करने के लिए घातीय समय की आवश्यकता होती है। सबसे पहले, इसका अर्थ P ≠ NP होगा, जो अभी भी एक अनसुलझा प्रश्न है। इसके अलावा, कुछ एनपी-पूर्ण समस्याओं में वास्तव में एल्गोरिदम सुपरपोलिनोमियल में चल रहे हैं, लेकिन उप-घातीय समय जैसे O(2^√nएन). उदाहरण के लिए, प्लानर ग्राफ़ के लिए इंडिपेंडेंट सेट प्रॉब्लम और डोमिनेटिंग सेट प्रॉब्लम प्रॉब्लम एनपी-पूर्ण हैं, लेकिन तलीय विभाजक प्रमेय का उपयोग करके उप-घातीय समय में हल किया जा सकता है।
• एनपी-पूर्ण समस्या का प्रत्येक उदाहरण कठिन है। अक्सर कुछ उदाहरण, या यहाँ तक कि अधिकांश उदाहरण, बहुपद समय के भीतर हल करना आसान हो सकते हैं। हालांकि, जब तक पी = एनपी, किसी भी बहुपद-समय एल्गोरिदम को एक निश्चित आकार के घातीय रूप से कई इनपुट बहुपद से अधिक पर असम्बद्ध रूप से गलत होना चाहिए।
• यदि पी = एनपी, सभी क्रिप्टोग्राफ़िक सिफर को तोड़ा जा सकता है। यदि बहुपद की डिग्री या स्थिरांक काफी बड़े हैं तो एक बहुपद-समय की समस्या को व्यवहार में हल करना बहुत कठिन हो सकता है। इसके अलावा, सूचना-सैद्धांतिक सुरक्षा क्रिप्टोग्राफ़िक तरीके प्रदान करती है जिसे असीमित कंप्यूटिंग शक्ति के साथ भी नहीं तोड़ा जा सकता है।
• एक बड़े पैमाने पर क्वांटम कंप्यूटर एनपी-पूर्ण समस्याओं को कुशलतापूर्वक हल करने में सक्षम होगा। निर्णय समस्याओं का वर्ग जिसे दोष-सहिष्णु क्वांटम कंप्यूटर द्वारा कुशलतापूर्वक (सिद्धांत रूप में) हल किया जा सकता है, बीक्यूपी के रूप में जाना जाता है। हालांकि, बीक्यूपी में सभी एनपी शामिल नहीं माना जाता है, और यदि ऐसा नहीं होता है, तो इसमें कोई एनपी-पूर्ण समस्या नहीं हो सकती है।

गुण

एक निर्णय समस्या को देखते हुए # कुछ निश्चित एन्कोडिंग में औपचारिक भाषा के रूप में परिभाषा, सभी एनपी-पूर्ण समस्याओं का सेट एनपीसी इसके तहत बंद नहीं है:

• संघ (सेट सिद्धांत)
• चौराहा
• जोड़
• क्लेन स्टार

यह ज्ञात नहीं है कि एनपीसी पूरक (जटिलता) के तहत बंद है, क्योंकि एनपीसी = [[सह-एनपी-पूर्ण]] | सह-एनपीसी अगर और केवल अगर एनपी = सह-एनपी, और क्या एनपी = सह-एनपी एक खुली समस्या है।

यह भी देखें

• लगभग पूरा
• गैजेट (कंप्यूटर विज्ञान)
• लेडनर की प्रमेय
• एनपी-पूर्ण समस्याओं की सूची
• एनपी-हार्ड
• पी = एनपी समस्या
• जोरदार एनपी-पूर्ण

ट्रैवलिंग सेल्समैन (2012 फ़िल्म)

संदर्भ

स्रोत

• Garey, M.R.; Johnson, D.S. (1979). कंप्यूटर और इंट्रेक्टेबिलिटी: एनपी-पूर्णता के सिद्धांत के लिए एक गाइड. New York: W.H. Freeman. ISBN 978-0-7167-1045-5. यह पुस्तक एक क्लासिक है, सिद्धांत विकसित कर रही है, फिर कई एनपी-पूर्ण समस्याओं को सूचीबद्ध करती है।
• Cook, S.A. (1971). "प्रमेय सिद्ध करने की प्रक्रियाओं की जटिलता". Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York. pp. 151–158. doi:10.1145/800157.805047.
• Dunne, P.E. "चयनित एनपी-पूर्ण समस्याओं की व्याख्या की गई सूची". COMP202, Dept. of Computer Science, University of Liverpool. Retrieved 2008-06-21.
• Crescenzi, P.; Kann, V.; Halldórsson, M.; Karpinski, M.; Woeginger, G. "एनपी अनुकूलन समस्याओं का एक संग्रह". KTH, Stockholm. Retrieved 2020-10-24.
• Dahlke, K. "एनपी-पूर्ण समस्याएं". Math Reference Project. Retrieved 2008-06-21.
• Karlsson, R. "व्याख्यान 8: एनपी-पूर्ण समस्याएँ" (PDF). Dept. of Computer Science, Lund University, Sweden. Archived from the original (PDF) on April 19, 2009. Retrieved 2008-06-21.
• Sun, H.M. "एनपी-पूर्णता का सिद्धांत". Information Security Laboratory, Dept. of Computer Science, National Tsing Hua University, Hsinchu City, Taiwan. Archived from the original (PPT) on 2009-09-02. Retrieved 2008-06-21.
• Jiang, J.R. "एनपी-पूर्णता का सिद्धांत" (PPT). Dept. of Computer Science and Information Engineering, National Central University, Jhongli City, Taiwan. Retrieved 2008-06-21.
• Cormen, T.H.; Leiserson, C.E.; Rivest, R.L.; Stein, C. (2001). "Chapter 34: NP–Completeness". एल्गोरिदम का परिचय (2nd ed.). MIT Press and McGraw-Hill. pp. 966–1021. ISBN 978-0-262-03293-3.
• Sipser, M. (1997). "Sections 7.4–7.5 (NP-completeness, Additional NP-complete Problems)". संगणना के सिद्धांत का परिचय. PWS Publishing. pp. 248–271. ISBN 978-0-534-94728-6.
• Papadimitriou, C. (1994). "Chapter 9 (NP-complete problems)". अभिकलनात्मक जटिलता (1st ed.). Addison Wesley. pp. 181–218. ISBN 978-0-201-53082-7.
• खेलों और पहेलियों की कम्प्यूटेशनल जटिलता
• टेट्रिस अनुमानित तक भी कठिन है
• माइनस्वीपर एनपी-पूर्ण है!
• Bern, Marshall (1990). "प्लानर नेटवर्क में स्टेनर ट्री के लिए तेज़ सटीक एल्गोरिदम". Networks. 20 (1): 109–120. doi:10.1002/net.3230200110..
• Deĭneko, Vladimir G.; Klinz, Bettina; Woeginger, Gerhard J. (2006). "प्लेनर ग्राफ में हैमिल्टनियन चक्र समस्या के लिए सटीक एल्गोरिदम". Operations Research Letters. 34 (3): 269–274. doi:10.1016/j.orl.2005.04.013..
• Dorn, Frederic; Penninkx, Eelko; Bodlaender, Hans L.; Fomin, Fedor V. (2005). "Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions". प्रक्रिया। एल्गोरिदम पर 13वीं यूरोपीय संगोष्ठी (ESA '05). Lecture Notes in Computer Science. Vol. 3669. Springer-Verlag. pp. 95–106. doi:10.1007/11561071_11. ISBN 978-3-540-29118-3..
• Lipton, Richard J.; Tarjan, Robert E. (1980). "एक तलीय विभाजक प्रमेय के अनुप्रयोग". SIAM Journal on Computing. 9 (3): 615–627. doi:10.1137/0209046. S2CID 12961628..

अग्रिम पठन

• Scott Aaronson, NP-complete Problems and Physical Reality, ACM SIGACT News, Vol. 36, No. 1. (March 2005), pp. 30–52.
• Lance Fortnow, The status of the P versus NP problem, Commun. ACM, Vol. 52, No. 9. (2009), pp. 78–86.