एनपी-पूर्णता और न्यूनीकरण

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

Definition

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

Scope

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

Core questions

• किसी समस्या के एनपी में सबसे कठिन समस्याओं में से एक होने का क्या अर्थ है?
• कुक-लेविन प्रमेय एक पहली एनपी-पूर्ण समस्या की पहचान कैसे करता है?
• एक नई समस्या को एनपी-पूर्ण सिद्ध करने के लिए न्यूनीकरण का उपयोग कैसे किया जाता है?
• एक समस्या की एनपी-पूर्णता के हजारों अन्य समस्याओं के लिए निहितार्थ क्यों होते हैं?

Key theories

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

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

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

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

Clinical relevance

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

History

कुक ने 1971 में संतुष्टि को एनपी-पूर्ण सिद्ध किया, और लेविन ने सोवियत संघ में स्वतंत्र रूप से समतुल्य परिणाम प्राप्त किए। 1972 में कार्प ने इक्कीस और एनपी-पूर्ण समस्याओं का प्रदर्शन किया, जिससे इस घटना की व्यापकता का पता चला और एनपी-पूर्णता संगणकीय कठिनाई के निदान के लिए केंद्रीय उपकरण बन गई।

Key figures

• Stephen Cook
• Leonid Levin
• Richard Karp

Seminal works

• cook1971
• karp1972

Frequently asked questions

एनपी का क्या अर्थ है?

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

आप एक नई समस्या को एनपी-पूर्ण कैसे सिद्ध करते हैं?

आप दो चीजें दिखाते हैं: कि समस्या एनपी में है, ताकि उम्मीदवार समाधानों की शीघ्रता से जांच की जा सके, और यह कि कुछ ज्ञात एनपी-पूर्ण समस्या बहुपद समय में इसमें न्यूनीकृत हो जाती है। न्यूनीकरण ज्ञात कठिनाई को स्थानांतरित करता है, नई समस्या को एनपी में सबसे कठिन समस्याओं में रखता है।