एनपी-पूर्णता और असाध्यता

एनपी-पूर्णता एनपी वर्ग में सबसे कठिन समस्याओं की पहचान करती है - वे समस्याएँ जिन पर प्रत्येक एनपी समस्या कम हो जाती है - और उन समस्याओं को पहचानने के लिए मानक ढाँचा प्रदान करती है जिनके लिए कोई कुशल एल्गोरिथम ज्ञात नहीं है या होने की संभावना नहीं है।

Definition

एक निर्णय समस्या एनपी-पूर्ण होती है यदि वह एनपी में निहित है (इसके 'हाँ'-उदाहरणों में कुशलता से सत्यापन योग्य प्रमाणपत्र होते हैं) और एनपी में प्रत्येक समस्या बहुपद समय में इस पर कम हो जाती है; ऐसी समस्याएँ एनपी में सबसे कठिन होती हैं, और किसी एक के लिए एक बहुपद-समय एल्गोरिथम सभी के लिए एक प्रदान करेगा।

Scope

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

Core questions

• जटिलता वर्ग पी और एनपी में क्या अंतर है?
• एक बहुपद-समय न्यूनीकरण एक समस्या से दूसरी समस्या में कठोरता को कैसे स्थानांतरित करता है?
• कुक-लेविन प्रमेय क्या स्थापित करता है, और संतुष्टि केंद्रीय क्यों है?
• एक ज्ञात समस्या से न्यूनीकरण द्वारा एक नई समस्या को एनपी-पूर्ण कैसे सिद्ध किया जाता है?
• एक बार जब कोई समस्या एनपी-कठोर सिद्ध हो जाती है, तो कौन सी एल्गोरिथम रणनीतियाँ शेष रहती हैं?

Key concepts

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

Key theories

कुक-लेविन प्रमेय

कुक-लेविन प्रमेय यह सिद्ध करता है कि बूलियन संतुष्टि (SAT) एनपी-पूर्ण है: एनपी में प्रत्येक समस्या बहुपद समय में इस पर कम हो जाती है, जो पहली एनपी-पूर्ण समस्या और दूसरों को कठिन साबित करने के लिए आधार प्रदान करती है।

संयोजनात्मक समस्याओं के बीच न्यूनीकरण

कार्प ने दिखाया कि बहुपद-समय न्यूनीकरण कई प्राकृतिक समस्याओं - क्लिक (clique), वर्टेक्स कवर (vertex cover), हैमिल्टनियन चक्र (Hamiltonian cycle), विभाजन (partition) और अन्य - को एनपी-पूर्ण समस्याओं के एक जाल में जोड़ते हैं, ताकि प्रत्येक को दूसरे से न्यूनीकरण द्वारा कठिन साबित किया जा सके।

Clinical relevance

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

History

स्टीफन कुक ने 1971 में एनपी-पूर्णता की शुरुआत की, एसएटी (SAT) को एनपी-पूर्ण साबित किया; लियोनिद लेविन स्वतंत्र रूप से इसी तरह के परिणामों पर पहुँचे। रिचर्ड कार्प के 1972 के पेपर ने 21 प्राकृतिक समस्याओं को एनपी-पूर्ण दिखाया, जिससे इस ढाँचे की पहुँच स्थापित हुई। गैरी और जॉनसन की 1979 की पुस्तक ने सैकड़ों एनपी-पूर्ण समस्याओं को सूचीबद्ध किया और मानक संदर्भ बन गई।

Debates

पी बनाम एनपी

क्या पी, एनपी के बराबर है - क्या प्रत्येक कुशलता से सत्यापन योग्य समस्या भी कुशलता से हल करने योग्य है - यह क्षेत्र में सबसे प्रमुख खुली समस्या है; लगभग सभी शोधकर्ता अनुमान लगाते हैं कि पी, एनपी के बराबर नहीं है, लेकिन यह प्रश्न अनसुलझा है और एक मिलेनियम पुरस्कार समस्या है।

Key figures

• Stephen Cook
• Richard Karp
• Leonid Levin
• Michael Garey
• David Johnson

Seminal works

• cook1971
• karp1972
• cormen2009

Frequently asked questions

एनपी-कठोर और एनपी-पूर्ण में क्या अंतर है?

एक समस्या एनपी-कठोर होती है यदि प्रत्येक एनपी समस्या बहुपद समय में इस पर कम हो जाती है, लेकिन इसे स्वयं एनपी में होने की आवश्यकता नहीं है और इसे निर्णय समस्या होने की भी आवश्यकता नहीं है। एक समस्या एनपी-पूर्ण होती है यदि वह एनपी-कठोर और एनपी दोनों में है। एनपी-पूर्ण समस्याएँ सबसे कठिन समस्याएँ हैं जो अभी भी एनपी में हैं।

क्या एनपी-पूर्णता का मतलब है कि किसी समस्या को कभी हल नहीं किया जा सकता है?

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