एनपी पूर्णता: Difference between revisions

Latest revision as of 14:54, 12 June 2023

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

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

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

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

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

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

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

सिंहावलोकन

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

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

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

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

$\scriptstyle C$ एनपी में है और
एनपी में हर समस्या बहुपद समय में $\scriptstyle C$ में कम हो जाती है।^[3]

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

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

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

पृष्ठभूमि

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

नामकरण

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

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

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

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

गुण

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

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

यह भी देखें

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

संदर्भ

उद्धरण

↑ For example, simply assigning true to each variable renders the 18th conjunct ${\overline {m}}\lor {\overline {r}}\lor {\overline {s}}$ (and hence the complete formula) false.
↑ Cobham, Alan (1965). "The intrinsic computational difficulty of functions". प्रक्रिया। तर्कशास्त्र, कार्यप्रणाली और विज्ञान का दर्शन II. North Holland.
↑ J. van Leeuwen (1998). सैद्धांतिक कंप्यूटर विज्ञान की पुस्तिका. Elsevier. p. 84. ISBN 978-0-262-72014-4.
↑ J. van Leeuwen (1998). सैद्धांतिक कंप्यूटर विज्ञान की पुस्तिका. Elsevier. p. 80. ISBN 978-0-262-72014-4.
↑ Kiersz, Andy. "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". Business Insider (in English). Retrieved 2023-04-24.
↑ Garey, Michael R.; Johnson, D. S. (1979). Victor Klee (ed.). Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. San Francisco, Calif.: W. H. Freeman and Co. pp. x+338. ISBN 978-0-7167-1045-5. MR 0519066.
↑ Agrawal, M.; Allender, E.; Rudich, Steven (1998). "Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem". Journal of Computer and System Sciences. 57 (2): 127–143. doi:10.1006/jcss.1998.1583. ISSN 1090-2724.
↑ Agrawal, M.; Allender, E.; Impagliazzo, R.; Pitassi, T.; Rudich, Steven (2001). "कटौती की जटिलता को कम करना". Computational Complexity. 10 (2): 117–138. doi:10.1007/s00037-001-8191-1. ISSN 1016-3328. S2CID 29017219.
↑ Don Knuth, Tracy Larrabee, and Paul M. Roberts, Mathematical Writing Archived 2010-08-27 at the Wayback Machine § 25, MAA Notes No. 14, MAA, 1989 (also Stanford Technical Report, 1987).
↑ ^10.0 ^10.1 Knuth, D. F. (1974). "A terminological proposal". SIGACT News. 6 (1): 12–18. doi:10.1145/1811129.1811130. S2CID 45313676.
↑ Ball, Philip (2000). "DNA computer helps travelling salesman". Nature. doi:10.1038/news000113-10.
↑ Bern (1990); Deĭneko, Klinz & Woeginger (2006); Dorn et al. (2005); Lipton & Tarjan (1980).
↑ Hemaspaandra, L. A.; Williams, R. (2012). "SIGACT News Complexity Theory Column 76". ACM SIGACT News. 43 (4): 70. doi:10.1145/2421119.2421135. S2CID 13367514.
↑ Aaronson, Scott (2010). "BQP and the polynomial hierarchy". In Schulman, Leonard J. (ed.). Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5–8 June 2010. Association for Computing Machinery. pp. 141–150. doi:10.1145/1806689.1806711.
↑ Talbot, John; Welsh, D. J. A. (2006), Complexity and Cryptography: An Introduction, Cambridge University Press, p. 57, ISBN 9780521617710, The question of whether NP and co-NP are equal is probably the second most important open problem in complexity theory, after the P versus NP question.

स्रोत

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.

[1] For example, simply assigning true to each variable renders the 18th conjunct ${\overline {m}}\lor {\overline {r}}\lor {\overline {s}}$ (and hence the complete formula) false.

[2] Cobham, Alan (1965). "The intrinsic computational difficulty of functions". प्रक्रिया। तर्कशास्त्र, कार्यप्रणाली और विज्ञान का दर्शन II. North Holland.

[3] J. van Leeuwen (1998). सैद्धांतिक कंप्यूटर विज्ञान की पुस्तिका. Elsevier. p. 84. ISBN 978-0-262-72014-4.

[4] J. van Leeuwen (1998). सैद्धांतिक कंप्यूटर विज्ञान की पुस्तिका. Elsevier. p. 80. ISBN 978-0-262-72014-4.

[5] Kiersz, Andy. "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". Business Insider (in English). Retrieved 2023-04-24.

[GareyJohnson-6] Garey, Michael R.; Johnson, D. S. (1979). Victor Klee (ed.). Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. San Francisco, Calif.: W. H. Freeman and Co. pp. x+338. ISBN 978-0-7167-1045-5. MR 0519066.

[7] Agrawal, M.; Allender, E.; Rudich, Steven (1998). "Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem". Journal of Computer and System Sciences. 57 (2): 127–143. doi:10.1006/jcss.1998.1583. ISSN 1090-2724.

[8] Agrawal, M.; Allender, E.; Impagliazzo, R.; Pitassi, T.; Rudich, Steven (2001). "कटौती की जटिलता को कम करना". Computational Complexity. 10 (2): 117–138. doi:10.1007/s00037-001-8191-1. ISSN 1016-3328. S2CID 29017219.

[9] Don Knuth, Tracy Larrabee, and Paul M. Roberts, Mathematical Writing Archived 2010-08-27 at the Wayback Machine § 25, MAA Notes No. 14, MAA, 1989 (also Stanford Technical Report, 1987).

[:0-10] 10.0 ^10.1 Knuth, D. F. (1974). "A terminological proposal". SIGACT News. 6 (1): 12–18. doi:10.1145/1811129.1811130. S2CID 45313676.

[11] Ball, Philip (2000). "DNA computer helps travelling salesman". Nature. doi:10.1038/news000113-10.

[12] Bern (1990); Deĭneko, Klinz & Woeginger (2006); Dorn et al. (2005); Lipton & Tarjan (1980).

[13] Hemaspaandra, L. A.; Williams, R. (2012). "SIGACT News Complexity Theory Column 76". ACM SIGACT News. 43 (4): 70. doi:10.1145/2421119.2421135. S2CID 13367514.

[14] Aaronson, Scott (2010). "BQP and the polynomial hierarchy". In Schulman, Leonard J. (ed.). Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5–8 June 2010. Association for Computing Machinery. pp. 141–150. doi:10.1145/1806689.1806711.

[15] Talbot, John; Welsh, D. J. A. (2006), Complexity and Cryptography: An Introduction, Cambridge University Press, p. 57, ISBN 9780521617710, The question of whether NP and co-NP are equal is probably the second most important open problem in complexity theory, after the P versus NP question.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

@@ Line 1: / Line 1: @@
 {{Short description|Complexity class}}
-[[File:3SAT 17 svg.svg|thumb|400px|बूलियन संतुष्टि की समस्या (एसएटी) यह निर्धारित करने के लिए कहती है कि क्या तर्कवाक्य सूत्र (उदाहरण दर्शाया गया है) को उसके चरों के लिए सत्य मानों के उपयुक्त असाइनमेंट (समाधान) द्वारा सत्य बनाया जा सकता है। हालांकि यह सत्यापित करना आसान है कि दिया गया असाइनमेंट सूत्र को सही बनाता है या नहीं,<ref>For example, simply assigning ''true'' to each variable renders the 18th conjunct <math>\overline{m} \lor \overline{r} \lor \overline{s}</math> (and hence the complete formula) ''false''.</ref> संतोषजनक असाइनमेंट खोजने के लिए अनिवार्य रूप से कोई तेज़ तरीका नहीं जाना जाता है, जो सभी असाइनमेंट को लगातार करने की कोशिश करता है। [[स्टीफन कुक]] और [[लियोनिद लेविन]] ने साबित किया कि प्रत्येक आसान-से-सत्यापित समस्या को एसएटी के रूप में तेजी से हल किया जा सकता है, जो कि एनपी-पूर्ण है।]][[कम्प्यूटेशनल जटिलता सिद्धांत]] में समस्या एनपी-पूर्ण होती है जब:
+[[File:3SAT 17 svg.svg|thumb|400px|बूलियन संतुष्टि की समस्या (एसएटी) यह निर्धारित करने के लिए कहती है कि क्या तर्कवाक्य सूत्र (उदाहरण दर्शाया गया है) को उसके चरों के लिए सत्य मानों के उपयुक्त असाइनमेंट (समाधान) द्वारा सत्य बनाया जा सकता है। चूँकि यह सत्यापित करना आसान है कि दिया गया असाइनमेंट सूत्र को सही बनाता है या नहीं,<ref>For example, simply assigning ''true'' to each variable renders the 18th conjunct <math>\overline{m} \lor \overline{r} \lor \overline{s}</math> (and hence the complete formula) ''false''.</ref> संतोषजनक असाइनमेंट खोजने के लिए अनिवार्य रूप से कोई तेज़ विधि नहीं जाना जाता है, जो सभी असाइनमेंट को लगातार करने की कोशिश करता है। [[स्टीफन कुक]] और [[लियोनिद लेविन]] ने सिद्ध किया कि प्रत्येक आसान-से-सत्यापित समस्या को एसएटी के रूप में तेजी से हल किया जा सकता है, जो कि एनपी-पूर्ण है।]][[कम्प्यूटेशनल जटिलता सिद्धांत]] में समस्या एनपी-पूर्ण होती है जब:
-# यह [[निर्णय समस्या]] है, जिसका अर्थ है कि समस्या के किसी भी इनपुट के लिए, आउटपुट या तो हाँ या नहीं है।
+# यह [[निर्णय समस्या]] है जिसका अर्थ है कि समस्या के किसी भी इनपुट के लिए, आउटपुट या तो हाँ या नहीं है।
-# जब उत्तर हां है, तो इसे छोटी (बहुपद लंबाई) 'समाधान' के अस्तित्व के माध्यम से प्रदर्शित किया जा सकता है।
+# जब उत्तर हां है तो इसे छोटी (बहुपद लंबाई) 'समाधान' के अस्तित्व के माध्यम से प्रदर्शित किया जा सकता है।
-# प्रत्येक समाधान की शुद्धता को जल्दी से सत्यापित किया जा सकता है (अर्थात्, बहुपद समय में) और [[क्रूर-बल खोज]] एल्गोरिदम सभी संभावित समाधानों का प्रयास करके समाधान ढूंढ सकता है।
+# प्रत्येक समाधान की शुद्धता को जल्दी से सत्यापित किया जा सकता है (अर्थात् बहुपद समय में) और [[क्रूर-बल खोज]] एल्गोरिदम सभी संभावित समाधानों का प्रयास करके समाधान खोज सकता है।
-# समस्या का उपयोग हर दूसरी समस्या का अनुकरण करने के लिए किया जा सकता है जिसके लिए हम जल्दी से सत्यापित कर सकते हैं कि समाधान सही है। इस अर्थ में, एनपी-पूर्ण समस्याएँ उन समस्याओं में सबसे कठिन हैं जिनके समाधानों को शीघ्रता से सत्यापित किया जा सकता है। अगर हम कुछ एनपी-पूर्ण समस्या का समाधान जल्दी से पा सकते हैं, तो हम जल्दी से हर दूसरी समस्या का समाधान खोज सकते हैं, जिसके लिए दिए गए समाधान को आसानी से सत्यापित किया जा सकता है।
+# समस्या का उपयोग हर दूसरी समस्या का अनुकरण करने के लिए किया जा सकता है जिसके लिए हम जल्दी से सत्यापित कर सकते हैं कि समाधान सही है। इस अर्थ में एनपी-पूर्ण समस्याएँ उन समस्याओं में सबसे कठिन हैं जिनके समाधानों को शीघ्रता से सत्यापित किया जा सकता है। यदि हम कुछ एनपी-पूर्ण समस्या का समाधान जल्दी से पा सकते हैं तो हम जल्दी से हर दूसरी समस्या का समाधान खोज सकते हैं जिसके लिए दिए गए समाधान को आसानी से सत्यापित किया जा सकता है।
-एनपी-पूर्ण नाम गैर-नियतात्मक बहुपद-समय पूर्ण के लिए छोटा है। इस नाम में, [[गैर-नियतात्मक ट्यूरिंग मशीन]]ों को संदर्भित करता है, जो जानवर-बल खोज एल्गोरिदम के विचार को गणितीय रूप से औपचारिक रूप देने का तरीका है। बहुपद समय उस समय की मात्रा को संदर्भित करता है जिसे समाधान की जांच करने के लिए [[नियतात्मक एल्गोरिथ्म]] के लिए त्वरित माना जाता है, या संपूर्ण खोज करने के लिए गैर-नियतात्मक ट्यूरिंग मशीन के लिए। [[पूर्ण (जटिलता)]] ही [[जटिलता वर्ग]] में सब कुछ अनुकरण करने में सक्षम होने की संपत्ति को संदर्भित करता है।
+एनपी-पूर्ण नाम गैर-नियतात्मक बहुपद-समय पूर्ण के लिए छोटा है। इस नाम में [[गैर-नियतात्मक ट्यूरिंग मशीन]] को संदर्भित करता है जो ब्रूट-बल खोज एल्गोरिदम के विचार को गणितीय रूप से औपचारिक रूप देने का विधि है। बहुपद समय उस समय की मात्रा को संदर्भित करता है जिसे समाधान की जांच करने के लिए [[नियतात्मक एल्गोरिथ्म]] के लिए त्वरित माना जाता है या संपूर्ण खोज करने के लिए गैर-नियतात्मक ट्यूरिंग मशीन के लिए [[पूर्ण (जटिलता)]] ही [[जटिलता वर्ग]] में सब कुछ अनुकरण करने में सक्षम होने की संपत्ति को संदर्भित करता है।
-अधिक सटीक रूप से, समस्या का प्रत्येक इनपुट बहुपद लंबाई के समाधान के सेट से जुड़ा होना चाहिए, जिसकी वैधता का शीघ्रता से परीक्षण किया जा सकता है (बहुपद समय में),<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> इस तरह कि किसी भी इनपुट के लिए आउटपुट हाँ है यदि समाधान सेट खाली नहीं है और नहीं तो यह खाली है। इस रूप की समस्याओं की जटिलता वर्ग को [[एनपी (जटिलता)]] कहा जाता है, जो गैर-नियतात्मक बहुपद समय के लिए संक्षिप्त नाम है। समस्या को [[ एनपी कठिन |एनपी कठिन]] कहा जाता है अगर एनपी में सब कुछ बहुपद समय में परिवर्तित हो सकता है, भले ही वह एनपी में न हो। इसके विपरीत, समस्या एनपी-पूर्ण है यदि यह एनपी और एनपी-हार्ड दोनों में है। एनपी-पूर्ण समस्याएं एनपी में सबसे कठिन समस्याओं का प्रतिनिधित्व करती हैं। अगर कुछ एनपी-पूर्ण समस्या में बहुपद समय एल्गोरिदम होता है, तो एनपी में सभी समस्याएं होती हैं। एनपी-पूर्ण समस्याओं का सेट अक्सर एनपी-सी या एनपीसी द्वारा निरूपित किया जाता है।
+अधिक स्पष्ट रूप से समस्या का प्रत्येक इनपुट बहुपद लंबाई के समाधान के सेट से जुड़ा होना चाहिए जिसकी वैधता का शीघ्रता से परीक्षण किया जा सकता है (बहुपद समय में)<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> इस तरह कि किसी भी इनपुट के लिए आउटपुट हाँ है यदि समाधान सेट खाली नहीं है और नहीं तो यह खाली है। इस रूप की समस्याओं की जटिलता वर्ग को [[एनपी (जटिलता)]] कहा जाता है जो गैर-नियतात्मक बहुपद समय के लिए संक्षिप्त नाम है। समस्या को [[ एनपी कठिन |एनपी हार्ड]] कहा जाता है यदि एनपी में सब कुछ बहुपद समय में परिवर्तित हो सकता है तथापि वह एनपी में न हो इसके विपरीत समस्या एनपी-पूर्ण है यदि यह एनपी और एनपी-हार्ड दोनों में है। एनपी-पूर्ण समस्याएं एनपी में सबसे कठिन समस्याओं का प्रतिनिधित्व करती हैं। यदि कुछ एनपी-पूर्ण समस्या में बहुपद समय एल्गोरिदम होता है तो एनपी में सभी समस्याएं होती हैं। एनपी-पूर्ण समस्याओं का सेट अधिकांशतः एनपी-सी या एनपीसी द्वारा निरूपित किया जाता है।
-हालांकि एनपी-पूर्ण समस्या का समाधान शीघ्रता से ''सत्यापित'' किया जा सकता है, लेकिन समाधान को शीघ्रता से ''ढूंढने'' का कोई ज्ञात तरीका नहीं है। अर्थात्, किसी भी वर्तमान में ज्ञात [[ कलन विधि |कलन विधि]] का उपयोग करके समस्या को हल करने के लिए आवश्यक समय तेजी से बढ़ता है क्योंकि समस्या का आकार बढ़ता है। नतीजतन, यह निर्धारित करना कि क्या इन समस्याओं को जल्दी से हल करना संभव है, जिसे [[पी बनाम एनपी समस्या]] कहा जाता है, आज कंप्यूटर विज्ञान में खुली समस्याओं की मौलिक सूची में से है।
+चूँकि एनपी-पूर्ण समस्या का समाधान शीघ्रता से ''सत्यापित'' किया जा सकता है किंतु समाधान को शीघ्रता से ''खोज ने'' का कोई ज्ञात विधि नहीं है। अर्थात् किसी भी वर्तमान में ज्ञात [[ कलन विधि |कलन विधि]] का उपयोग करके समस्या को हल करने के लिए आवश्यक समय तेजी से बढ़ता है क्योंकि समस्या का आकार बढ़ता है। परिणाम स्वरुप यह निर्धारित करना कि क्या इन समस्याओं को जल्दी से हल करना संभव है जिसे [[पी बनाम एनपी समस्या]] कहा जाता है आज कंप्यूटर विज्ञान में विवर्त समस्याओं की मौलिक सूची में से है।
-जबकि एनपी-पूर्ण समस्याओं के समाधान की गणना करने का तरीका जल्दी से अनदेखा रहता है, कंप्यूटर वैज्ञानिक और [[कंप्यूटर प्रोग्राम]]र अभी भी अक्सर एनपी-पूर्ण समस्याओं का सामना करते हैं। एनपी-पूर्ण समस्याओं को अक्सर ह्यूरिस्टिक (कंप्यूटर विज्ञान) विधियों और सन्निकटन एल्गोरिदम का उपयोग करके संबोधित किया जाता है।
+जबकि एनपी-पूर्ण समस्याओं के समाधान की गणना करने का विधि जल्दी से अनदेखा रहता है कंप्यूटर वैज्ञानिक और [[कंप्यूटर प्रोग्राम]]र अभी भी अधिकांशतः एनपी-पूर्ण समस्याओं का सामना करते हैं। एनपी-पूर्ण समस्याओं को अधिकांशतः ह्यूरिस्टिक (कंप्यूटर विज्ञान) विधियों और सन्निकटन एल्गोरिदम का उपयोग करके संबोधित किया जाता है।
 == सिंहावलोकन ==
-एनपी-पूर्ण समस्याएं एनपी (जटिलता) में हैं, सभी निर्णय समस्याओं का सेट जिनके समाधान बहुपद समय में सत्यापित किए जा सकते हैं; एनपी को समान रूप से निर्णय समस्याओं के सेट के रूप में परिभाषित किया जा सकता है जिसे [[गैर-नियतात्मक ट्यूरिंग मशीन]] पर बहुपद समय में हल किया जा सकता है। एनपी में समस्या पी एनपी-पूर्ण है अगर एनपी में हर दूसरी समस्या बहुपद समय में पी में परिवर्तित (या कम) हो सकती है।
+एनपी-पूर्ण समस्याएं एनपी (जटिलता) में हैं सभी निर्णय समस्याओं का सेट जिनके समाधान बहुपद समय में सत्यापित किए जा सकते हैं एनपी को समान रूप से निर्णय समस्याओं के सेट के रूप में परिभाषित किया जा सकता है जिसे [[गैर-नियतात्मक ट्यूरिंग मशीन]] पर बहुपद समय में हल किया जा सकता है। एनपी में समस्या पी एनपी-पूर्ण है यदि एनपी में हर दूसरी समस्या बहुपद समय में पी में परिवर्तित (या कम) हो सकती है।
-यह ज्ञात नहीं है कि एनपी में हर समस्या को जल्दी से हल किया जा सकता है या नहीं - इसे पी बनाम एनपी समस्या कहा जाता है। लेकिन अगर किसी एनपी-पूर्ण समस्या को जल्दी से हल किया जा सकता है, तो एनपी में हर समस्या हो सकती है, क्योंकि एनपी-पूर्ण समस्या की परिभाषा बताती है कि एनपी में हर समस्या को हर एनपी-पूर्ण समस्या के लिए शीघ्रता से कम किया जाना चाहिए (अर्थात, यह कर सकते हैं) बहुपद समय में घटाया जा सकता है)। इस वजह से, अक्सर यह कहा जाता है कि एनपी-पूर्ण समस्याएं सामान्य रूप से एनपी समस्याओं से कठिन या अधिक कठिन होती हैं।
+यह ज्ञात नहीं है कि एनपी में हर समस्या को जल्दी से हल किया जा सकता है या नहीं - इसे पी बनाम एनपी समस्या कहा जाता है। किंतु यदि किसी एनपी-पूर्ण समस्या को जल्दी से हल किया जा सकता है तो एनपी में हर समस्या हो सकती है क्योंकि एनपी-पूर्ण समस्या की परिभाषा बताती है कि एनपी में हर समस्या को हर एनपी-पूर्ण समस्या के लिए शीघ्रता से कम किया जाना चाहिए (अर्थात यह कर सकते हैं) बहुपद समय में घटाया जा सकता है)। इस वजह से अधिकांशतः यह कहा जाता है कि एनपी-पूर्ण समस्याएं सामान्य रूप से एनपी समस्याओं से कठिन या अधिक कठिन होती हैं।
 == औपचारिक परिभाषा ==
-{{See also |P %3D NP problem#NP-completeness |l1 = formal definition for NP-completeness (article ''P = NP'')}}
+{{See also |पी% 3डी एनपी समस्या या एनपी-पूर्णता|l1 = एनपी-पूर्णता के लिए औपचारिक परिभाषा (लेख ''P = NP'')}}
-एक निर्णय समस्या <math>\scriptstyle C</math> एनपी-पूर्ण है अगर:
+एक निर्णय समस्या <math>\scriptstyle C</math> एनपी-पूर्ण है यदि :
-# <math>\scriptstyle C</math> एनपी में है, और
+# <math>\scriptstyle C</math> एनपी में है और
-# एनपी में हर समस्या कई-एक कमी है <math>\scriptstyle C</math> बहुपद समय में।<ref>{{cite book |author = J. van Leeuwen |year = 1998 |title = सैद्धांतिक कंप्यूटर विज्ञान की पुस्तिका|publisher = Elsevier |isbn = 978-0-262-72014-4 |page = 84}}</ref>
+#एनपी में हर समस्या बहुपद समय में <math>\scriptstyle C</math> में कम हो जाती है।<ref>{{cite book |author = J. van Leeuwen |year = 1998 |title = सैद्धांतिक कंप्यूटर विज्ञान की पुस्तिका|publisher = Elsevier |isbn = 978-0-262-72014-4 |page = 84}}</ref>
-<math>\scriptstyle C</math> एनपी में यह प्रदर्शित करके दिखाया जा सकता है कि उम्मीदवार समाधान <math>\scriptstyle C</math> बहुपद समय में सत्यापित किया जा सकता है।
+<math>\scriptstyle C</math> को NP में यह प्रदर्शित करके दिखाया जा सकता है कि <math>\scriptstyle C</math> का उम्मीदवार समाधान बहुपद समय में सत्यापित किया जा सकता है।
-ध्यान दें कि स्थिति 2 को संतुष्ट करने वाली समस्या को एनपी-हार्ड कहा जाता है, चाहे वह स्थिति 1 को संतुष्ट करती हो या नहीं।<ref>{{cite book |author = J. van Leeuwen |year = 1998 |title = सैद्धांतिक कंप्यूटर विज्ञान की पुस्तिका|publisher = Elsevier |isbn = 978-0-262-72014-4 |page = 80}}</ref>
+ध्यान दें कि स्थिति 2 को संतुष्ट करने वाली समस्या को एनपी-हार्ड कहा जाता है चाहे वह स्थिति 1 को संतुष्ट करती हो या नहीं।<ref>{{cite book |author = J. van Leeuwen |year = 1998 |title = सैद्धांतिक कंप्यूटर विज्ञान की पुस्तिका|publisher = Elsevier |isbn = 978-0-262-72014-4 |page = 80}}</ref>
-इस परिभाषा का परिणाम यह है कि यदि हमारे पास बहुपद समय एल्गोरिथ्म था (एक [[यूनिवर्सल ट्यूरिंग मशीन]] पर, या किसी अन्य [[ट्यूरिंग पूर्णता]] | ट्यूरिंग-समतुल्य सार मशीन) के लिए <math>\scriptstyle C</math>, हम एनपी में सभी समस्याओं को बहुपद समय में हल कर सकते हैं।
+इस परिभाषा का एक परिणाम यह है कि यदि हमारे पास <math>\scriptstyle C</math> के लिए एक बहुपद समय एल्गोरिथ्म (एक [[यूनिवर्सल ट्यूरिंग मशीन]] या किसी अन्य ट्यूरिंग-समतुल्य अमूर्त मशीन पर) होता है तो हम बहुपद समय में NP में सभी समस्याओं को हल कर सकते हैं।
 == पृष्ठभूमि ==
-[[File:P np np-complete np-hard.svg|thumb|300px|right|[[पी (जटिलता)]], एनपी (जटिलता), एनपी-पूर्ण, और एनपी-हार्ड समस्याओं के सेट के लिए [[यूलर आरेख]]। बायां पक्ष इस धारणा के तहत मान्य है कि पी बनाम एनपी समस्या | पी ≠ एनपी, जबकि दायां पक्ष इस धारणा के तहत मान्य है कि पी = एनपी (सिवाय इसके कि खाली भाषा और इसके पूरक कभी भी एनपी-पूर्ण नहीं होते हैं, और सामान्य तौर पर, पी या एनपी में हर समस्या एनपी-पूर्ण नहीं है)]]एनपी-पूर्णता की अवधारणा को 1971 में पेश किया गया था (कुक-लेविन प्रमेय देखें), हालांकि एनपी-पूर्ण शब्द बाद में पेश किया गया था। कम्प्यूटिंग सम्मेलन के सिद्धांत पर 1971 की संगोष्ठी में, कंप्यूटर वैज्ञानिकों के बीच इस बात को लेकर तीखी बहस हुई कि क्या [[नियतात्मक]] [[ट्यूरिंग मशीन]] पर एनपी-पूर्ण समस्याओं को बहुपद समय में हल किया जा सकता है। [[जॉन हॉपक्रॉफ्ट]] ने सम्मेलन में सभी को आम सहमति के लिए लाया कि क्या एनपी-पूर्ण समस्याएं बहुपद समय में हल करने योग्य हैं या नहीं, कुछ बाद की तारीख में हल करने के लिए बंद कर दिया जाना चाहिए, क्योंकि किसी के पास उनके दावों के लिए कोई औपचारिक सबूत नहीं था या दूसरा . इसे P=NP के प्रश्न के रूप में जाना जाता है।
+[[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>
+एनपी-पूर्ण समस्याओं का अस्तित्व स्पष्ट नहीं है। कुक-लेविन प्रमेय कहता है कि बूलियन संतुष्टि समस्या एनपी-पूर्ण है इस प्रकार यह स्थापित करता है कि ऐसी समस्याएं उपस्थित हैं। 1972 में [[रिचर्ड कार्प]] ने सिद्ध किया कि कई अन्य समस्याएं भी एनपी-पूर्ण थीं (कार्प की 21 एनपी-पूर्ण समस्याएं देखें) इस प्रकार एनपी-पूर्ण समस्याओं का वर्ग है (बूलियन संतुष्टि समस्या के अतिरिक्त )। मूल परिणामों के बाद से हजारों अन्य समस्याओं को एनपी-पूर्ण दिखाया गया है, अन्य समस्याओं को पहले एनपी-पूर्ण दिखाया गया है; इनमें से कई समस्याओं को [[माइकल गैरी]] और डेविड एस. जॉनसन की 1979 की पुस्तक कंप्यूटर्स एंड इंट्रेक्टेबिलिटी: ए गाइड टू द थ्योरी ऑफ एनपी-कम्प्लीटनेस में संकलित किया गया है।<ref name="GareyJohnson">{{cite book |last1=Garey |first1=Michael&nbsp;R. |author-link1=Michael R. Garey |last2=Johnson |first2=D.&nbsp;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.&nbsp;H.&nbsp;Freeman and Co. |location=San Francisco, Calif. |mr=519066 |title-link=Computers and Intractability: A Guide to the Theory of NP-Completeness }}</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 एनपी-पूर्ण समस्याएं देखें); इस प्रकार, एनपी-पूर्ण समस्याओं का वर्ग है (बूलियन संतुष्टि समस्या के अलावा)। मूल परिणामों के बाद से, हजारों अन्य समस्याओं को एनपी-पूर्ण दिखाया गया है, अन्य समस्याओं को पहले एनपी-पूर्ण दिखाया गया है; इनमें से कई समस्याओं को [[माइकल गैरी]] और डेविड एस. जॉनसन|जॉनसन की 1979 की पुस्तक कंप्यूटर्स एंड इंट्रेक्टेबिलिटी: ए गाइड टू द थ्योरी ऑफ एनपी-कम्प्लीटनेस में संकलित किया गया है।<ref name="GareyJohnson">{{cite book |last1=Garey |first1=Michael&nbsp;R. |author-link1=Michael R. Garey |last2=Johnson |first2=D.&nbsp;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.&nbsp;H.&nbsp;Freeman and Co. |location=San Francisco, Calif. |mr=519066 |title-link=Computers and Intractability: A Guide to the Theory of NP-Completeness }}</ref>
 == एनपी-पूर्ण समस्याएं ==
-[[File:Relative NPC chart.svg|thumb|300px|right|कुछ एनपी-पूर्ण समस्याएं, [[कमी (जटिलता)]] का संकेत देते हुए आमतौर पर उनकी एनपी-पूर्णता साबित करने के लिए उपयोग की जाती हैं]]
+[[File:Relative NPC chart.svg|thumb|300px|right|कुछ एनपी-पूर्ण समस्याएं, [[कमी (जटिलता)]] का संकेत देते हुए सामान्यतः उनकी एनपी-पूर्णता सिद्ध करने के लिए उपयोग की जाती हैं]]
-{{Main|List of NP-complete problems}}
+{{Main|एनपी-पूर्ण समस्याओं की सूची}}
-यह साबित करने का सबसे आसान तरीका है कि कुछ नई समस्या एनपी-पूर्ण है, पहले यह साबित करना है कि यह एनपी में है, और फिर कुछ ज्ञात एनपी-पूर्ण समस्या को कम करना है। इसलिए, विभिन्न प्रकार की एनपी-पूर्ण समस्याओं को जानना उपयोगी है। नीचे दी गई सूची में कुछ प्रसिद्ध समस्याएं हैं जो निर्णय समस्याओं के रूप में व्यक्त किए जाने पर एनपी-पूर्ण हैं।
+यह सिद्ध करने का सबसे आसान विधि है कि कुछ नई समस्या एनपी-पूर्ण है पहले यह सिद्ध करना है कि यह एनपी में है और फिर कुछ ज्ञात एनपी-पूर्ण समस्या को कम करना है। इसलिए विभिन्न प्रकार की एनपी-पूर्ण समस्याओं को जानना उपयोगी है। नीचे दी गई सूची में कुछ प्रसिद्ध समस्याएं हैं जो निर्णय समस्याओं के रूप में व्यक्त किए जाने पर एनपी-पूर्ण हैं।
 {{div col|colwidth=25em}}
 * बूलियन संतुष्टि समस्या | बूलियन संतुष्टि समस्या (SAT)
@@ Line 57: / Line 60: @@
 {{div col end}}
-दाईं ओर कुछ समस्याओं का आरेख है और कमी (जटिलता) आमतौर पर उनकी एनपी-पूर्णता साबित करने के लिए उपयोग की जाती है। इस डायग्राम में समस्याओं को नीचे से ऊपर की ओर कम किया गया है। ध्यान दें कि यह आरेख इन समस्याओं के बीच गणितीय संबंध के विवरण के रूप में भ्रामक है, क्योंकि किसी भी दो एनपी-पूर्ण समस्याओं के बीच [[बहुपद-समय में कमी]] मौजूद है; लेकिन यह इंगित करता है कि इस बहुपद-समय में कमी को प्रदर्शित करना सबसे आसान कहां रहा है।
+दाईं ओर कुछ समस्याओं का आरेख है और कमी (जटिलता) सामान्यतः उनकी एनपी-पूर्णता सिद्ध करने के लिए उपयोग की जाती है। इस डायग्राम में समस्याओं को नीचे से ऊपर की ओर कम किया गया है। ध्यान दें कि यह आरेख इन समस्याओं के बीच गणितीय संबंध के विवरण के रूप में भ्रामक है क्योंकि किसी भी दो एनपी-पूर्ण समस्याओं के बीच [[बहुपद-समय में कमी]] उपस्थित है किंतु यह इंगित करता है कि इस बहुपद-समय में कमी को प्रदर्शित करना सबसे आसान कहां रहा है।
-पी और एनपी-पूर्ण समस्या में समस्या के बीच अक्सर केवल छोटा सा अंतर होता है। उदाहरण के लिए, 3-संतोषजनक समस्या, बूलियन संतुष्टि समस्या का प्रतिबंध, एनपी-पूर्ण रहता है, जबकि थोड़ा अधिक प्रतिबंधित 2-संतोषजनक समस्या पी में है (विशेष रूप से, यह [[एनएल-पूर्ण]] है), लेकिन थोड़ा अधिक सामान्य अधिकतम . 2-शनि. समस्या फिर से एनपी-पूर्ण है। यह निर्धारित करना कि ग्राफ़ को 2 रंगों से रंगा जा सकता है या नहीं, P में है, लेकिन 3 रंगों के साथ NP-पूर्ण है, भले ही वह समतलीय ग्राफ़ तक सीमित हो। यह निर्धारित करना कि कोई ग्राफ़ [[चक्र ग्राफ]]़ है या द्विदलीय ग्राफ़ बहुत आसान है ([[एल (जटिलता)]] में), लेकिन अधिकतम द्विदलीय या अधिकतम चक्र सबग्राफ खोजना एनपी-पूर्ण है। इष्टतम समाधान के किसी भी निश्चित प्रतिशत के भीतर नैपसैक समस्या का समाधान बहुपद समय में गणना किया जा सकता है, लेकिन इष्टतम समाधान खोजना एनपी-पूर्ण है।
+पी और एनपी-पूर्ण समस्या में समस्या के बीच अधिकांशतः केवल छोटा सा अंतर होता है। उदाहरण के लिए 3-संतोषजनक समस्या बूलियन संतुष्टि समस्या का प्रतिबंध एनपी-पूर्ण रहता है जबकि थोड़ा अधिक प्रतिबंधित 2-संतोषजनक समस्या पी में है (विशेष रूप से यह [[एनएल-पूर्ण]] है) किंतु थोड़ा अधिक सामान्य अधिकतम . 2-शनि. समस्या फिर से एनपी-पूर्ण है। यह निर्धारित करना कि ग्राफ़ को 2 रंगों से रंगा जा सकता है या नहीं, P में है, किंतु 3 रंगों के साथ NP-पूर्ण है तथापि वह समतलीय ग्राफ़ तक सीमित हो। यह निर्धारित करना कि कोई ग्राफ़ [[चक्र ग्राफ]] है या द्विदलीय ग्राफ़ बहुत आसान है ([[एल (जटिलता)]] में) किंतु अधिकतम द्विदलीय या अधिकतम चक्र सबग्राफ खोजना एनपी-पूर्ण है। इष्टतम समाधान के किसी भी निश्चित प्रतिशत के अंदर नैपसैक समस्या का समाधान बहुपद समय में गणना किया जा सकता है किंतु इष्टतम समाधान खोजना एनपी-पूर्ण है।
 === इंटरमीडिएट समस्याएं ===
-एक दिलचस्प उदाहरण [[ग्राफ समरूपता]] समस्या है, यह निर्धारित करने की [[ग्राफ सिद्धांत]] समस्या है कि दो ग्राफों के बीच ग्राफ समरूपता मौजूद है या नहीं। दो ग्राफ़ [[समरूपी]] हैं यदि को वर्टेक्स (ग्राफ़ सिद्धांत) का नाम बदलकर दूसरे में [[समाकृतिकता]] हो सकता है। इन दो समस्याओं पर विचार करें:
+एक रौचक उदाहरण [[ग्राफ समरूपता]] समस्या है यह निर्धारित करने की [[ग्राफ सिद्धांत]] समस्या है कि दो ग्राफों के बीच ग्राफ समरूपता उपस्थित है या नहीं दो ग्राफ़ [[समरूपी]] हैं यदि को वर्टेक्स (ग्राफ़ सिद्धांत) का नाम बदलकर दूसरे में [[समाकृतिकता]] हो सकता है। इन दो समस्याओं पर विचार करें:
-* ग्राफ समरूपता: क्या ग्राफ जी है<sub>1</sub> ग्राफ जी के लिए आइसोमोर्फिक<sub>2</sub>?
+*ग्राफ़ समरूपता: क्या ग्राफ़ G<sub>1</sub> ग्राफ़ G<sub>2</sub> के तुल्याकार है?
-* सबग्राफ समरूपता: क्या ग्राफ जी है<sub>1</sub> ग्राफ जी के सबग्राफ के लिए आइसोमोर्फिक<sub>2</sub>?
+*सबग्राफ तुल्याकारिता: क्या ग्राफ़ G<sub>1</sub> ग्राफ़ G<sub>2</sub> के सबग्राफ़ के तुल्याकार है?
-सबग्राफ समरूपता समस्या एनपी-पूर्ण है। ग्राफ समरूपता समस्या न तो पी और न ही एनपी-पूर्ण होने का संदेह है, हालांकि यह एनपी में है। यह ऐसी समस्या का उदाहरण है जिसे कठिन माना जाता है, लेकिन एनपी-पूर्ण नहीं माना जाता है। इस वर्ग को एनपी-इंटरमीडिएट समस्याएं कहा जाता है और मौजूद है अगर और केवल अगर पी≠एनपी।
+सबग्राफ समरूपता समस्या एनपी-पूर्ण है। ग्राफ समरूपता समस्या न तो पी और न ही एनपी-पूर्ण होने का संदेह है चूँकि यह एनपी में है। यह ऐसी समस्या का उदाहरण है जिसे कठिन माना जाता है किंतु एनपी-पूर्ण नहीं माना जाता है। इस वर्ग को एनपी-इंटरमीडिएट समस्याएं कहा जाता है और उपस्थित है यदि और केवल यदि P≠NP।
 == एनपी-पूर्ण समस्याओं का समाधान ==
-वर्तमान में, एनपी-पूर्ण समस्याओं के लिए सभी ज्ञात एल्गोरिदम में समय की आवश्यकता होती है जो वास्तव में इनपुट आकार में [[ अधिबहुपद |अधिबहुपद]] है {{clarify span|exponential in <math>O(n^k)</math>|reason=Replace by a single expression in Big-O notation, like (guessed) O(2^(n^k)).|date=July 2021}} कुछ के लिए <math>k>0</math> और यह अज्ञात है कि क्या कोई तेज़ एल्गोरिथम हैं।
+वर्तमान में एनपी-पूर्ण समस्याओं के लिए सभी ज्ञात एल्गोरिदम के लिए समय की आवश्यकता होती है जो इनपुट आकार में [[ अधिबहुपद |अधिबहुपद]] है वास्तव में {{clarify span|exponential in <math>O(n^k)</math>|reason=Replace by a single expression in Big-O notation, like (guessed) O(2^(n^k)).|date=July 2021}}में कुछ <math>k>0</math> के लिए एक्सपोनेंशियल है और यह अज्ञात है कि क्या कोई तेज एल्गोरिदम है ।
-सामान्य रूप से कम्प्यूटेशनल समस्याओं को हल करने के लिए निम्नलिखित तकनीकों को लागू किया जा सकता है, और वे अक्सर काफी तेज एल्गोरिदम को जन्म देते हैं:
+सामान्य रूप से कम्प्यूटेशनल समस्याओं को हल करने के लिए निम्नलिखित विधियों को प्रयुक्त किया जा सकता है और वे अधिकांशतः अधिक तेज एल्गोरिदम को जन्म देते हैं:
-* [[जेनेटिक एल्गोरिद्म]]: इष्टतम समाधान खोजने के बजाय, ऐसे समाधान की खोज करें जो इष्टतम से अधिक से अधिक कारक हो।
+* [[जेनेटिक एल्गोरिद्म]]: इष्टतम समाधान खोजने के अतिरिक्त ऐसे समाधान की खोज करें जो इष्टतम से अधिक से अधिक कारक हो।
-* [[ यादृच्छिक एल्गोरिदम ]]: तेजी से चलने वाले औसत समय को प्राप्त करने के लिए रैंडमनेस का उपयोग करें, और एल्गोरिथ्म को कुछ छोटी संभावना के साथ विफल होने दें। नोट[[मोंटे कार्लो विधि]] पद्धति इस विशिष्ट अर्थ में कुशल एल्गोरिथम का उदाहरण नहीं है, हालांकि आनुवंशिक एल्गोरिदम जैसे विकासवादी दृष्टिकोण हो सकते हैं।
+* [[ यादृच्छिक एल्गोरिदम ]]: तेजी से चलने वाले औसत समय को प्राप्त करने के लिए रैंडमनेस का उपयोग करें और एल्गोरिथ्म को कुछ छोटी संभावना के साथ विफल होने दें। नोट[[मोंटे कार्लो विधि]] पद्धति इस विशिष्ट अर्थ में कुशल एल्गोरिथम का उदाहरण नहीं है चूँकि आनुवंशिक एल्गोरिदम जैसे विकासवादी दृष्टिकोण हो सकते हैं।
-* प्रतिबंध: इनपुट की संरचना को प्रतिबंधित करके (उदाहरण के लिए, प्लानर ग्राफ़ के लिए), तेज़ एल्गोरिदम आमतौर पर संभव होते हैं।
+* प्रतिबंध: इनपुट की संरचना को प्रतिबंधित करके (उदाहरण के लिए प्लानर ग्राफ़ के लिए) तेज़ एल्गोरिदम सामान्यतः संभव होते हैं।
-* [[पैरामीटरयुक्त जटिलता]]: यदि इनपुट के कुछ पैरामीटर निश्चित हैं तो अक्सर तेज़ एल्गोरिदम होते हैं।
+* [[पैरामीटरयुक्त जटिलता]]: यदि इनपुट के कुछ पैरामीटर निश्चित हैं तो अधिकांशतः तेज़ एल्गोरिदम होते हैं।
-* ह्यूरिस्टिक (कंप्यूटर विज्ञान): एल्गोरिथ्म जो कई मामलों में यथोचित रूप से अच्छी तरह से काम करता है, लेकिन इसके लिए कोई प्रमाण नहीं है कि यह हमेशा तेज़ होता है और हमेशा अच्छा परिणाम देता है। [[मेटाह्यूरिस्टिक]] दृष्टिकोण अक्सर उपयोग किए जाते हैं।
+* ह्यूरिस्टिक (कंप्यूटर विज्ञान): एल्गोरिथ्म जो कई स्थिति में यथोचित रूप से अच्छी तरह से काम करता है किंतु इसके लिए कोई प्रमाण नहीं है कि यह सदैव तेज़ होता है और सदैव अच्छा परिणाम देता है। [[मेटाह्यूरिस्टिक]] दृष्टिकोण अधिकांशतः उपयोग किए जाते हैं।
-एक अनुमानी एल्गोरिथम का उदाहरण उपइष्टतम है <math>O(n\log n)</math> [[लालची रंग]] कुछ कंपाइलरों के रजिस्टर आवंटन चरण के दौरान ग्राफ रंग की समस्या के लिए उपयोग किया जाता है, तकनीक जिसे [[ग्राफ-रंग वैश्विक रजिस्टर आवंटन]] कहा जाता है। प्रत्येक शीर्ष चर है, किनारों को उन चरों के बीच खींचा जाता है जो ही समय में उपयोग किए जा रहे हैं, और रंग प्रत्येक चर को निर्दिष्ट रजिस्टर को इंगित करते हैं। चूंकि अधिकांश [[ जोखिम |जोखिम]] मशीनों में काफी बड़ी संख्या में सामान्य-उद्देश्य [[आवंटन रजिस्टर करें]] हैं, यहां तक कि अनुमानी दृष्टिकोण भी इस आवेदन के लिए प्रभावी है।
+हेयुरिस्टिक एल्गोरिथम का एक उदाहरण एक सबऑप्टिमल <math>O(n\log n)</math> लालची कलरिंग एल्गोरिथम है जिसका उपयोग कुछ कंपाइलरों के रजिस्टर आवंटन चरण के समय ग्राफ़ कलरिंग के लिए किया जाता है, एक विधि जिसे ग्राफ़-कलरिंग ग्लोबल रजिस्टर एलोकेशन कहा जाता है। प्रत्येक शीर्ष एक चर है किनारों को उन चरों के बीच खींचा जाता है जो एक ही समय में उपयोग किए जा रहे हैं और रंग प्रत्येक चर को निर्दिष्ट रजिस्टर को इंगित करते हैं। चूंकि अधिकांश आरआईएससी मशीनों में अधिक बड़ी संख्या में सामान्य-उद्देश्य रजिस्टर होते हैं यहां तक कि एक अनुमानी दृष्टिकोण भी इस आवेदन के लिए प्रभावी है।
 == विभिन्न प्रकार की कमी के तहत पूर्णता ==
 ऊपर दी गई एनपी-पूर्ण की परिभाषा में, बहुपद-समय कई-एक कमी के तकनीकी अर्थ में कमी शब्द का उपयोग किया गया था।
-एक अन्य प्रकार की कमी बहुपद-समय ट्यूरिंग कमी है। समस्या <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> हालाँकि, यह ज्ञात है कि AC0|AC<sup>0</sup> कटौती बहुपद-समय कटौती की तुलना में सख्ती से छोटी कक्षा को परिभाषित करती है।<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 }}
 </ref>
 == नामकरण ==
-[[डोनाल्ड नुथ]] के अनुसार, एनपी-पूर्ण नाम को [[ मैं अल्फ्रेड हूं |मैं अल्फ्रेड हूं]] , जॉन होपक्रॉफ्ट और [[जेफरी उल्मैन]] ने अपनी प्रसिद्ध पाठ्यपुस्तक द डिजाइन एंड एनालिसिस ऑफ कंप्यूटर एल्गोरिदम में लोकप्रिय बनाया था। वह रिपोर्ट करता है कि उन्होंने किताब के लिए [[गैली प्रूफ]] में बदलाव पेश किया (बहुपद-पूर्ण से), [[सैद्धांतिक कंप्यूटर विज्ञान]] समुदाय के सर्वेक्षण के परिणामों के अनुसार।<ref>[[Don Knuth]], Tracy Larrabee, and Paul M. Roberts, ''[http://tex.loria.fr/typographie/mathwriting.pdf Mathematical Writing] {{Webarchive|url=https://web.archive.org/web/20100827044400/http://tex.loria.fr/typographie/mathwriting.pdf |date=2010-08-27 }}'' § 25, ''MAA Notes No. 14'', MAA, 1989 (also [[Stanford University|Stanford]] Technical Report, 1987).</ref> पोल में किए गए अन्य सुझाव<ref>{{Cite journal
+[[डोनाल्ड नुथ]] के अनुसार "एनपी-पूर्ण" नाम को अल्फ्रेड अहो जॉन होपक्रॉफ्ट और [[जेफरी उल्मैन]] ने अपनी प्रसिद्ध पाठ्यपुस्तक "कंप्यूटर एल्गोरिदम का डिजाइन और विश्लेषण" में लोकप्रिय बनाया था। वह सूचित करता है कि उन्होंने सैद्धांतिक कंप्यूटर विज्ञान समुदाय के एक सर्वेक्षण के परिणामों के अनुसार पुस्तक के लिए गैली प्रूफ ("बहुपद-पूर्ण") में बदलाव प्रस्तुत किया। पोल में किए गए अन्य सुझावों में सम्मिलित हैं<ref>[[Don Knuth]], Tracy Larrabee, and Paul M. Roberts, ''[http://tex.loria.fr/typographie/mathwriting.pdf Mathematical Writing] {{Webarchive|url=https://web.archive.org/web/20100827044400/http://tex.loria.fr/typographie/mathwriting.pdf |date=2010-08-27 }}'' § 25, ''MAA Notes No. 14'', MAA, 1989 (also [[Stanford University|Stanford]] Technical Report, 1987).</ref> "अत्यंत कठिन" "दुर्जेय" कुक के सम्मान में स्टिग्लिट्ज़ का "हार्ड-बोल्ड" और शेन लिन का परिवर्णी शब्द "पीईटी" जो "संभवतः घातीय समय" के लिए खड़ा था<ref name=":0">{{Cite journal
 |doi = 10.1145/1811129.1811130
 |volume = 6
@@ Line 104: / Line 105: @@
 |year = 1974
 |s2cid = 45313676
-}}</ref> [[हरक्यूलिस के मजदूर]], दुर्जेय, कुक के सम्मान में [[केनेथ स्टिग्लिट्ज़]] की कड़ी मेहनत, और शेन लिन का संक्षिप्त नाम पीईटी शामिल है, जो शायद घातीय समय के लिए खड़ा था, लेकिन पी बनाम एनपी समस्या किस तरह से चली गई, इसके आधार पर इसका मतलब हो सकता है{{sic|hide=y|provably}} चरघातांकी समय या पूर्व चरघातांकी समय ।<ref>See the poll, or [http://www.cs.princeton.edu/~wayne/kleinberg-tardos/08np-complete-2x2.pdf] {{Webarchive|url=https://web.archive.org/web/20110607082034/http://www.cs.princeton.edu/~wayne/kleinberg-tardos/08np-complete-2x2.pdf|date=2011-06-07}}.</ref>
+}}</ref> किंतु यह इस बात पर निर्भर करता है कि किस तरह से पी बनाम एनपी समस्या चली गई "सिद्ध रूप से घातीय समय" या "पहले घातीय समय" के लिए खड़ा हो सकता है।<ref name=":0" />
+== सामान्य गलतफहमी ==
+निम्नलिखित गलत धारणाएं अधिकांशतः होती हैं।<ref>{{Cite news|url=http://www.nature.com/news/2000/000113/full/news000113-10.html
-== आम गलतफहमी ==
-निम्नलिखित गलत धारणाएं अक्सर होती हैं।<ref>{{Cite news|url=http://www.nature.com/news/2000/000113/full/news000113-10.html
 |doi = 10.1038/news000113-10
 |title = DNA computer helps travelling salesman
@@ Line 114: / Line 113: @@
 |journal = Nature
 |year = 2000
-}}</ref> * एनपी-पूर्ण समस्याएँ सबसे कठिन ज्ञात समस्याएँ हैं। चूंकि एनपी-पूर्ण समस्याएं एनपी में हैं, उनका चलने का समय सबसे अधिक घातीय है। हालाँकि, कुछ समस्याओं के लिए अधिक समय की आवश्यकता साबित हुई है, उदाहरण के लिए प्रेसबर्गर अंकगणित। कुछ समस्याओं में से, यह भी सिद्ध हो चुका है कि उन्हें कभी भी हल नहीं किया जा सकता है, उदाहरण के लिए [[रुकने की समस्या]]।
+}}</ref> * एनपी-पूर्ण समस्याएँ सबसे कठिन ज्ञात समस्याएँ हैं। चूंकि एनपी-पूर्ण समस्याएं एनपी में हैं उनका चलने का समय सबसे अधिक घातीय है। चूँकि कुछ समस्याओं के लिए अधिक समय की आवश्यकता सिद्ध हुई है उदाहरण के लिए प्रेसबर्गर अंकगणित कुछ समस्याओं में से यह भी सिद्ध हो चुका है कि उन्हें कभी भी हल नहीं किया जा सकता है उदाहरण के लिए [[रुकने की समस्या]]।
-* एनपी-पूर्ण समस्याएँ कठिन हैं क्योंकि बहुत सारे अलग-अलग समाधान हैं। ओर, ऐसी कई समस्याएं हैं जिनका समाधान स्थान उतना ही बड़ा है, लेकिन बहुपद समय में हल किया जा सकता है (उदाहरण के लिए न्यूनतम फैले पेड़)। दूसरी ओर, अधिकांश समाधान के साथ एनपी-समस्याएं हैं जो यादृच्छिक बहुपद-समय में कमी के तहत एनपी-हार्ड हैं (देखें वैलेंट-वजीरानी प्रमेय)।
+* एनपी-पूर्ण समस्याएँ कठिन हैं क्योंकि बहुत सारे अलग-अलग समाधान हैं। ओर ऐसी कई समस्याएं हैं जिनका समाधान स्थान उतना ही बड़ा है किंतु बहुपद समय में हल किया जा सकता है (उदाहरण के लिए न्यूनतम फैले पेड़)। दूसरी ओर अधिकांश समाधान के साथ एनपी-समस्याएं हैं जो यादृच्छिक बहुपद-समय में कमी के तहत एनपी-हार्ड हैं (देखें वैलेंट-वजीरानी प्रमेय)।
-* एनपी-पूर्ण समस्याओं को हल करने के लिए घातीय समय की आवश्यकता होती है। सबसे पहले, इसका अर्थ P ≠ NP होगा, जो अभी भी अनसुलझा प्रश्न है। इसके अलावा, कुछ एनपी-पूर्ण समस्याओं में वास्तव में एल्गोरिदम सुपरपोलिनोमियल में चल रहे हैं, लेकिन उप-घातीय समय जैसे O(2<sup>{{sqrt|''n''}}</sup>एन). उदाहरण के लिए, प्लानर ग्राफ़ के लिए इंडिपेंडेंट सेट प्रॉब्लम और डोमिनेटिंग सेट प्रॉब्लम प्रॉब्लम एनपी-पूर्ण हैं, लेकिन [[तलीय विभाजक प्रमेय]] का उपयोग करके उप-घातीय समय में हल किया जा सकता है।<ref>{{harvtxt|Bern|1990}}; {{harvtxt|Deĭneko|Klinz|Woeginger|2006}}; {{harvtxt|Dorn|Penninks|Bodlaender|Fomin|2005}}; {{harvtxt|Lipton|Tarjan|1980}}.</ref>
+* एनपी-पूर्ण समस्याओं को हल करने के लिए घातीय समय की आवश्यकता होती है। सबसे पहले इसका अर्थ P ≠ NP होगा जो अभी भी अनसुलझा प्रश्न है। इसके अतिरिक्त कुछ एनपी-पूर्ण समस्याओं में वास्तव में एल्गोरिदम सुपरपोलिनोमियल में चल रहे हैं किंतु उप-घातीय समय जैसे O(2<sup>{{sqrt|''n''}}</sup>''n)'' उदाहरण के लिए प्लानर ग्राफ़ के लिए इंडिपेंडेंट सेट समस्या और डोमिनेटिंग सेट समस्या समस्या एनपी-पूर्ण हैं किंतु [[तलीय विभाजक प्रमेय]] का उपयोग करके उप-घातीय समय में हल किया जा सकता है।<ref>{{harvtxt|Bern|1990}}; {{harvtxt|Deĭneko|Klinz|Woeginger|2006}}; {{harvtxt|Dorn|Penninks|Bodlaender|Fomin|2005}}; {{harvtxt|Lipton|Tarjan|1980}}.</ref>
-* एनपी-पूर्ण समस्या का प्रत्येक उदाहरण कठिन है। अक्सर कुछ उदाहरण, या यहाँ तक कि अधिकांश उदाहरण, बहुपद समय के भीतर हल करना आसान हो सकते हैं। हालांकि, जब तक पी = एनपी, किसी भी बहुपद-समय एल्गोरिदम को निश्चित आकार के घातीय रूप से कई इनपुट बहुपद से अधिक पर असम्बद्ध रूप से गलत होना चाहिए।<ref>{{Cite journal | last1 = Hemaspaandra | first1 = L. A. | last2 = Williams | first2 = R. | doi = 10.1145/2421119.2421135 | title = SIGACT News Complexity Theory Column 76 | journal = ACM SIGACT News | volume = 43 | issue = 4 | page = 70 | year = 2012 | s2cid = 13367514 }}</ref>
+* एनपी-पूर्ण समस्या का प्रत्येक उदाहरण कठिन है। अधिकांशतः कुछ उदाहरण या यहाँ तक कि अधिकांश उदाहरण बहुपद समय के अंदर हल करना आसान हो सकते हैं। चूँकि जब तक पी = एनपी किसी भी बहुपद-समय एल्गोरिदम को निश्चित आकार के घातीय रूप से कई इनपुट बहुपद से अधिक पर असम्बद्ध रूप से गलत होना चाहिए।<ref>{{Cite journal | last1 = Hemaspaandra | first1 = L. A. | last2 = Williams | first2 = R. | doi = 10.1145/2421119.2421135 | title = SIGACT News Complexity Theory Column 76 | journal = ACM SIGACT News | volume = 43 | issue = 4 | page = 70 | year = 2012 | s2cid = 13367514 }}</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>
+* एक बड़े मापदंड पर क्वांटम कंप्यूटर एनपी-पूर्ण समस्याओं को कुशलतापूर्वक हल करने में सक्षम होगा। निर्णय समस्याओं का वर्ग जिसे दोष-सहिष्णु क्वांटम कंप्यूटर द्वारा कुशलतापूर्वक (सिद्धांत रूप में) हल किया जा सकता है बीक्यूपी के रूप में जाना जाता है। चूँकि बीक्यूपी में सभी एनपी सम्मिलित नहीं माना जाता है और यदि ऐसा नहीं होता है तो इसमें कोई एनपी-पूर्ण समस्या नहीं हो सकती है।<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>
+== गुण                                                       ==
+एक निर्णय समस्या को देखते हुए या कुछ निश्चित एन्कोडिंग में औपचारिक भाषा के रूप में परिभाषा सभी एनपी-पूर्ण समस्याओं का सेट एनपीसी इसके तहत बंद नहीं है:
-== गुण ==
-एक निर्णय समस्या को देखते हुए # कुछ निश्चित एन्कोडिंग में औपचारिक भाषा के रूप में परिभाषा, सभी एनपी-पूर्ण समस्याओं का सेट एनपीसी इसके तहत बंद नहीं है:
 * [[संघ (सेट सिद्धांत)]]
-* [[चौराहा]]
+* [[चौराहा|प्रतिच्छेदन]]
 * जोड़
-* [[क्लेन स्टार]]{{example needed|Give a counter example for each of the set operations.|date=April 2023}}
+* [[क्लेन स्टार]]
+यह ज्ञात नहीं है कि एनपीसी पूरक के तहत बंद है क्योंकि एनपीसी = सह-एनपीसी यदि और केवल यदि एनपी = सह-एनपी और क्या एनपी = सह-एनपी एक [[खुली समस्या|विवर्त]] प्रश्न है।<ref>{{citation |title = Complexity and Cryptography: An Introduction |first1 = John |last1 = Talbot|first2=D. J. A.|last2 = Welsh |author2-link = Dominic Welsh |publisher = Cambridge University Press |year = 2006 |isbn = 9780521617710 |page=57 |url = https://books.google.com/books?id=y_ZwupY8pzUC&pg=PA57 |quote = The question of whether NP and co-NP are equal is probably the second most important open problem in complexity theory, after the P versus NP question.}}</ref>
-यह ज्ञात नहीं है कि एनपीसी [[पूरक (जटिलता)]] के तहत बंद है, क्योंकि एनपीसी = [[[[सह-एनपी]]-पूर्ण]] | सह-एनपीसी अगर और केवल अगर एनपी = सह-एनपी, और क्या एनपी = सह-एनपी [[खुली समस्या]] है।<ref>{{citation |title = Complexity and Cryptography: An Introduction |first1 = John |last1 = Talbot|first2=D. J. A.|last2 = Welsh |author2-link = Dominic Welsh |publisher = Cambridge University Press |year = 2006 |isbn = 9780521617710 |page=57 |url = https://books.google.com/books?id=y_ZwupY8pzUC&pg=PA57 |quote = The question of whether NP and co-NP are equal is probably the second most important open problem in complexity theory, after the P versus NP question.}}</ref>
 == यह भी देखें ==
 * [[लगभग पूरा]]
@@ Line 311: / Line 305: @@
 {{ComplexityClasses}}
-{{DEFAULTSORT:Np-Complete}}[[Category: कंप्यूटिंग में 1971]] [[Category: एनपी-पूर्ण समस्याएं | एनपी-पूर्ण समस्याएं ]] [[Category: जटिलता वर्ग]] [[Category: गणितीय अनुकूलन]]
+{{DEFAULTSORT:Np-Complete}}
-[[Category: Machine Translated Page]]
+[[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]]

v t e Important complexity classes (more)
Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP APX FP
Suspected infeasible	UP NP NP-complete NP-hard co-NP co-NP-complete AM QMA PH ⊕P PP #P #P-complete IP PSPACE PSPACE-complete
Considered infeasible	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY PR R RE ALL
Class hierarchies	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetical hierarchy Boolean hierarchy
Families of classes	DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system

Anonymous

Search

एनपी पूर्णता: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 14:54, 12 June 2023

Contents

सिंहावलोकन

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

पृष्ठभूमि