P बनाम NP समस्या

P बनाम NP समस्या यह पूछती है कि क्या हर वह समस्या जिसके समाधानों को शीघ्रता से सत्यापित किया जा सकता है, उसे शीघ्रता से हल भी किया जा सकता है। यह सैद्धांतिक कंप्यूटर विज्ञान का केंद्रीय अनुत्तरित प्रश्न है और क्ले मिलेनियम पुरस्कार समस्याओं में से एक है।

Definition

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

Scope

यह विषय P बनाम NP के औपचारिक कथन, किसी भी NP-पूर्ण समस्या के लिए बहुपद-समय एल्गोरिथम होने के साथ इसकी समानता, दोनों उत्तरों के परिणाम, सापेक्षता (relativization), प्राकृतिक प्रमाण (natural proofs), और बीजगणित (algebrization) जैसी बाधाएँ जिन्होंने प्रगति को अवरुद्ध किया है, और व्यापक अनुमान कि ये वर्ग भिन्न हैं, को शामिल करता है।

Core questions

• क्या किसी समाधान को खोजना उसे जाँचने से मौलिक रूप से कठिन है?
• उत्तर इस बात पर क्यों निर्भर करता है कि क्या कोई एकल NP-पूर्ण समस्या P में है?
• यदि P, NP के बराबर होता, और यदि नहीं होता, तो दुनिया कैसी दिखती?
• दशकों के प्रयासों के बावजूद इस प्रश्न को हल करने में विफलता क्यों मिली है?

Key theories

NP-पूर्णता के साथ समानता

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

प्रमाण बाधाएँ

सापेक्षता (relativization), प्राकृतिक प्रमाण (natural proofs), और बीजगणित (algebrization) के परिणाम दर्शाते हैं कि मुख्य ज्ञात प्रमाण तकनीकें P बनाम NP को हल नहीं कर सकती हैं, जो कठिनाई को समझाते हैं और मौलिक रूप से नई विधियों की खोज का मार्गदर्शन करते हैं।

Clinical relevance

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

History

कुक ने 1971 में NP-पूर्णता के साथ इस प्रश्न को तैयार किया, और इसे शीघ्र ही मौलिक के रूप में मान्यता मिली। 1980 के दशक में सर्किट लोअर बाउंड्स (circuit lower bounds) के माध्यम से किए गए प्रयासों को रज़बोरोव और रुडिच द्वारा पहचानी गई प्राकृतिक-प्रमाण बाधा का सामना करना पड़ा, और 2000 में क्ले मैथमेटिक्स इंस्टीट्यूट ने इसे दस लाख डॉलर के पुरस्कार के साथ मिलेनियम पुरस्कार समस्या के रूप में नामित किया।

Debates

क्या P बनाम NP कभी हल होगा, और इसका उत्तर क्या है?

अधिकांश शोधकर्ता अनुमान लगाते हैं कि P, NP के बराबर नहीं है, लेकिन कोई प्रमाण मौजूद नहीं है और ज्ञात तकनीकें स्पष्ट रूप से अपर्याप्त हैं। इस बात पर राय भिन्न हैं कि क्या समाधान निकट है, क्या इसके लिए मौलिक रूप से नए गणित की आवश्यकता है, या क्या यह प्रश्न मानक अभिगृहीतों से स्वतंत्र भी हो सकता है।

Key figures

• Stephen Cook
• Leonid Levin
• Richard Karp
• Alexander Razborov

Seminal works

• cook1971
• aroraBarak2009

Frequently asked questions

यदि P, NP के बराबर होता तो क्या होता?

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

यह समस्या हल करने में इतनी कठिन क्यों है?

P, NP के बराबर है यह साबित करने के लिए एक NP-पूर्ण समस्या के लिए एक तेज़ एल्गोरिथम की आवश्यकता है, जिसे किसी ने नहीं खोजा है; यह साबित करने के लिए कि वे भिन्न हैं, यह दिखाना होगा कि ऐसा कोई एल्गोरिथम मौजूद नहीं हो सकता है। सापेक्षता (relativization) और प्राकृतिक प्रमाण (natural proofs) पर परिणाम दर्शाते हैं कि मानक तकनीकें बाद वाले को स्थापित करने में स्वाभाविक रूप से असमर्थ हैं, इसलिए एक वास्तव में नए दृष्टिकोण की आवश्यकता है।