एनपी पूर्णता

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

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

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

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

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

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

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

सिंहावलोकन

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

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

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

See also: एनपी-पूर्णता के लिए औपचारिक परिभाषा (लेख P = NP)

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

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

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

ध्यान दें कि स्थिति 2 को संतुष्ट करने वाली समस्या को एनपी-हार्ड कहा जाता है चाहे वह स्थिति 1 को संतुष्ट करती हो या नहीं।

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

पृष्ठभूमि

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

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

कोई भी अभी तक निर्णायक रूप से यह निर्धारित करने में सक्षम नहीं है कि क्या एनपी-पूर्ण समस्याएं वास्तव में बहुपद समय में हल करने योग्य हैं यह गणित की महान अनसुलझी समस्याओं में से है। मिट्टी गणित संस्थान किसी को भी $1 मिलियन का इनाम दे रहा है जिसके पास P=NP या P≠NP का औपचारिक प्रमाण है।

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

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

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

Main article: एनपी-पूर्ण समस्याओं की सूची

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

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

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

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

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

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

• ग्राफ़ समरूपता: क्या ग्राफ़ G₁ ग्राफ़ G₂ के तुल्याकार है?
• सबग्राफ तुल्याकारिता: क्या ग्राफ़ G₁ ग्राफ़ G₂ के सबग्राफ़ के तुल्याकार है?

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

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

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

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

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

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

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

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

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

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

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

नामकरण

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

सामान्य गलतफहमी

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

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

गुण

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

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

यह ज्ञात नहीं है कि एनपीसी पूरक के तहत बंद है क्योंकि एनपीसी = सह-एनपीसी यदि और केवल यदि एनपी = सह-एनपी और क्या एनपी = सह-एनपी एक विवर्त प्रश्न है।

यह भी देखें

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

ट्रैवलिंग सेल्समैन (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.