कंप्यूटर विज्ञान की सबसे बड़ी समस्या: P बनाम NP
सात गणितीय समस्याएँ ऐसी हैं, जिन्हें इतना कठिन और रोचक माना गया कि क्ले गणित संस्थान (Clay Mathematics Institute) ने उन्हें मिलेनियम पुरस्कार समस्याएँ घोषित किया। इनमें से हर समस्या को हल करने वाले को दस लाख डॉलर का पुरस्कार मिलेगा। इनमें से एक समस्या कंप्यूटर विज्ञान से भी जुड़ी है और इसे P बनाम NP समस्या कहते हैं। आइए, समझें कि यह समस्या वास्तव में किस बारे में है।
तो बात यह है। हम ख़ुद को यह धोखा नहीं देंगे कि इसे समझाना आसान होगा। आख़िर यह मिलेनियम समस्या है। इसलिए एक कप अच्छी हरी चाय 🍵 बना लीजिए और शुरू करते हैं। पहले हम कंप्यूटर विज्ञान और एल्गोरिद्म की दुनिया की चार अलग-अलग समस्याएँ देखेंगे। हम इन समस्याओं का विश्लेषण करेंगे और देखेंगे कि इनका अक्षरों P और NP से क्या संबंध है।
समस्या 1: सबसे छोटी संख्या ढूँढ़ना
P बनाम NP एल्गोरिद्म और उनकी जटिलता से संबंधित है। कल्पना कीजिए कि मैं आपके सामने कागज़ की सौ पर्चियाँ बिखेर दूँ, हर पर्ची पर एक संख्या लिखी हो, और आपसे कहूँ कि वह पर्ची ढूँढ़िए जिस पर सबसे छोटी संख्या लिखी है। आपको इसमें कितना समय लगेगा?
आधा मिनट? दो मिनट?
सैद्धांतिक कंप्यूटर विज्ञान में समय की इन इकाइयों में हमारी ज़्यादा रुचि नहीं है। हमारी रुचि बल्कि संक्रियाओं की संख्या में है। इसलिए हम प्रश्न थोड़ा अलग तरह से पूछ सकते हैं: मुझे कितनी पर्चियाँ जाँचनी होंगी, ताकि मुझे निश्चित रूप से पता हो कि मैंने सबसे छोटी संख्या ढूँढ़ ली है? उत्तर है कि मुझे सभी पर्चियाँ जाँचनी होंगी, क्योंकि सबसे छोटी संख्या आख़िरी पर्ची पर भी हो सकती है। यदि मैं आपके सामने सौ पर्चियाँ डालूँ, तो आपको सौ पर्चियाँ जाँचनी होंगी। यदि हज़ार डालूँ, तो हज़ार जाँचनी होंगी। व्यापक रूप में, यदि मैं आपके सामने n पर्चियाँ डालूँ, तो आपको n पर्चियाँ जाँचनी होंगी।
इसे हम एल्गोरिद्म की जटिलता कहते हैं। यदि मैं आपके सामने n पर्चियाँ डालूँ और सबसे छोटी संख्या ढूँढ़ने के लिए आपको n संक्रियाएँ करनी पड़ें, तो इसका अर्थ है कि सबसे छोटी संख्या ढूँढ़ने वाले इस एल्गोरिद्म की जटिलता n है। इसे रैखिक जटिलता भी कहते हैं, क्योंकि जटिलता एक रैखिक फलन से व्यक्त होती है।
ठीक है, आपने सौ पर्चियाँ देखीं और बताया कि सबसे छोटी संख्या 17 है। मैं कैसे जाँचूँ कि आप सच कह रहे हैं? इसके अलावा कोई तरीका नहीं है कि मैं फिर से सभी पर्चियाँ देखूँ और जाँचूँ कि किसी पर भी इससे छोटी संख्या नहीं है। यानी सबसे छोटी संख्या ढूँढ़ने के लिए आपको n पर्चियाँ देखनी पड़ती हैं, और जब मैं इसे जाँचना चाहूँ, तो मुझे भी यही करना पड़ता है। इसलिए परिणाम के सत्यापन की जटिलता भी n है, यानी रैखिक जटिलता।
क्या ऐसे एल्गोरिद्म भी हैं, जिनमें परिणाम ढूँढ़ने की तुलना में उसकी जाँच करना आसान हो?
समस्या 2: जोड़ी का गुणनफल
कल्पना कीजिए कि मैं आपके सामने पर्चियों की समान आकार की दो ढेरियाँ बिखेर दूँ, और हर पर्ची पर फिर एक संख्या हो। अब मैं चाहता हूँ कि आप ढेरी A से एक संख्या और ढेरी B से एक संख्या ऐसी ढूँढ़ें कि उनका गुणनफल 918 हो। उदाहरण के लिए, संख्याओं की ढेरियाँ ये हैं:
ऐसी संख्याओं की जोड़ी कैसे ढूँढ़ें, जिनका गुणनफल 918 के बराबर हो? हम बस सभी विकल्प आज़मा सकते हैं। ये कितने होंगे? काफ़ी सारे, 25। शुरुआत में ढेरी A की पहली संख्या, यानी 49, को ढेरी B की हर संख्या से गुणा करते हैं:
किसी भी जोड़ी से 918 नहीं मिलता। इसलिए ढेरी A की बाकी संख्याओं के साथ भी यही करते हैं, यानी संख्या 11 के लिए पाँच और जोड़ियाँ, संख्या 32 के लिए पाँच और, 54 के लिए पाँच और, और 15 के लिए अंतिम पाँच जोड़ियाँ। कुल मिलाकर हम संख्याओं की 25 जोड़ियाँ आज़मा सकते हैं। अंत में पता चलता है कि 54 · 17 = 918।
इस एल्गोरिद्म की जटिलता क्या है? हमारी रुचि इसमें होगी कि हमें संख्याओं की कितनी जोड़ियों का गुणा करना पड़ा। दोनों ढेरियों में पाँच-पाँच पर्चियाँ थीं, और हमें पहली ढेरी की पाँचों संख्याओं में से हर एक को दूसरी ढेरी की पाँचों संख्याओं में से हर एक के साथ आज़माना पड़ा। कुल मिलाकर हमने 5 · 5 = 25 संयोजन आज़माए। यदि मैं आपके सामने 10-10 पर्चियों की दो ढेरियाँ डालता, तो आपको 10 · 10 = 100 संयोजन आज़माने पड़ते। व्यापक रूप में, यदि मैं आपके सामने n पर्चियों वाली दो ढेरियाँ डालूँ, तो आपको n · n = n2 संयोजन आज़माने होंगे।
हम कहेंगे कि हमारे इस एल्गोरिद्म की जटिलता n2 है, यानी द्विघाती जटिलता, क्योंकि यह द्विघात फलन से व्यक्त होती है।
पर परिणाम की जाँच कितनी जटिल होगी? यदि आप मुझे बताएँ कि 54 और 17 वे संख्याएँ हैं जिनका गुणनफल 918 है, तो मुझे दोनों ढेरियों की सभी जोड़ियाँ नहीं देखनी पड़तीं, जैसे आपको देखनी पड़ी थीं। मेरे लिए इतना काफ़ी है कि मैं इस एक जोड़ी 54 · 17 का गुणा करूँ, और मुझे पता चल जाएगा कि आप सही हैं या नहीं। यानी इस समस्या को हल करने के लिए n2 तक गुणनफल निकालने पड़ते हैं, जबकि सत्यापन के लिए केवल एक गुणनफल काफ़ी है। इसलिए सत्यापन की जटिलता अचर 1 है।
यहीं यह प्रश्न पिछले प्रश्न से काफ़ी अलग है, जिसमें गणना और उसके बाद के सत्यापन, दोनों में बराबर चरण लगते थे।
यह प्रश्न पिछले प्रश्न से कहीं अधिक जटिल भी है। यदि मैं आपके सामने दस हज़ार पर्चियाँ बिखेरकर सबसे छोटी संख्या ढूँढ़ने को कहूँ, तो शायद आप उसे एक दिन में ढूँढ़ लें। पर यदि मैं आपके सामने दस-दस हज़ार पर्चियों की दो ढेरियाँ बिखेरकर गुणनफल ढूँढ़ने को कहूँ, तो आपको दस हज़ार गुणा दस हज़ार गुणनफल जाँचने होंगे, यानी दस करोड़ गणनाएँ। यदि आप हर सेकंड एक गुणनफल निकालें, तब भी आपको लगभग तीन साल लगेंगे।
समस्या 3: उपसमुच्चय का योग
आइए, तीसरी समस्या देखें। इस बार मैं आपके सामने संख्याओं वाली बारह पर्चियाँ बिखेरता हूँ और चाहता हूँ कि आप कितनी भी पर्चियाँ ऐसी ढूँढ़ें, जिनका योग शून्य हो। उदाहरण के लिए:
इन संख्याओं में से संख्याओं का कोई भी ऐसा समूह चुनिए, जिसका योग 0 हो। उदाहरण के लिए, संख्याओं
का योग 4 है, इसलिए यह सही उत्तर नहीं है। सही उत्तर संख्याओं का समूह है… और पता है क्या? इसे गृहकार्य के रूप में ख़ुद ढूँढ़िए 😉। संख्याओं का केवल एक समूह ऐसा है, जिसका योग 0 है। कम से कम आप यह तो अनुभव कर लेंगे कि यह समस्या कितनी कठिन है।
अब हमें इस समस्या की जटिलता जाननी है। इसकी गणना अब उतनी आसान नहीं है और यह गहरी रुचि रखने वालों के लिए है। यदि आप जानना चाहते हैं कि इस समस्या की जटिलता कैसे निकाली जाती है, तो पढ़ते रहिए। नहीं तो आप अगले खंड पर जा सकते हैं। ⏩
तो हम संख्याओं का ऐसा समूह कैसे ढूँढ़ें, जिसका योग 0 हो? हमें बस संख्याओं के सभी संभव संचय आज़माने होंगे। हमें संख्याओं की सभी जोड़ियाँ, सभी तिकड़ियाँ, चौकड़ियाँ, पाँच-पाँच के समूह आदि आज़माने होंगे, और हर समूह के लिए जाँचना होगा कि उसका योग शून्य है या नहीं। ऐसे कितने संचय हैं?
आइए, इसे संख्याओं के एक छोटे समुच्चय पर देखें। तीन संख्याओं B = {5, 7, 9} से मैं संख्याओं के कितने अलग-अलग समूह, यानी उपसमुच्चय, बना सकता हूँ? कुल आठ:
ध्यान दीजिए कि हमने रिक्त उपसमुच्चय B1 को भी गिना है। अभी यह बहुत उपयोगी नहीं है, पर पूर्णता के लिए हमने इसे रखा है। गणना को सरल बनाने के लिए हम हर उपसमुच्चय को एक द्विआधारी सदिश (binary vector) देंगे। द्विआधारी सदिश बस शून्यों और इकाइयों का एक अनुक्रम है, जैसे 00101010। हम लंबाई तीन वाले द्विआधारी सदिशों के साथ काम करेंगे। सदिश हम इस तरह देते हैं: 101 उस उपसमुच्चय को देते हैं, जिसमें “दिए गए समुच्चय की पहली और तीसरी संख्या है, पर दूसरी नहीं”, यानी समुच्चय {5, 9} को। सदिश 110 उस उपसमुच्चय को देते हैं, जिसमें “दिए गए समुच्चय की पहली और दूसरी संख्या है, पर तीसरी नहीं”, यानी समुच्चय {5, 7} को, आदि।
हम देखते हैं कि हर उपसमुच्चय का लंबाई तीन वाला एक ही द्विआधारी सदिश है। और लंबाई तीन वाला हर द्विआधारी सदिश एक ही उपसमुच्चय के संगत है। अतः यदि हम गिन लें कि लंबाई n वाले कितने अलग-अलग द्विआधारी सदिश हैं, तो हमें उन अलग-अलग संचयों की संख्या मिल जाएगी, जो n अलग-अलग संख्याओं से बनाए जा सकते हैं। आइए, इसे गिनें।
लंबाई एक वाले द्विआधारी सदिश दो हैं: 0 और 1।
लंबाई दो वाले द्विआधारी सदिश ऐसे मिलते हैं: लंबाई एक वाले सभी द्विआधारी सदिश लीजिए और हर सदिश के अंत में 0 जोड़िए: सदिश 00 और 10 मिलते हैं। फिर से लंबाई 1 वाले सभी सदिश लीजिए और अंत में 1 जोड़िए: 01 और 11। इस तरह हमें लंबाई 2 वाले सभी सदिश मिल गए: 00, 01, 10 और 11।
लंबाई तीन वाले द्विआधारी सदिश ऐसे मिलते हैं: लंबाई दो वाले सभी द्विआधारी सदिश लीजिए और अंत में शून्य जोड़िए: 000, 010, 100 और 110, और फिर इकाई जोड़िए: 001, 011, 101 और 111।
और इसी तरह हर अगली लंबाई के लिए। हम देखते हैं कि द्विआधारी सदिश की लंबाई एक बढ़ाने पर अलग-अलग द्विआधारी सदिशों की संख्या दोगुनी हो जाती है। इसलिए सदिश की लंबाई चार के लिए हमें कुल 2 · 2 · 2 · 2, यानी 16, अलग-अलग संचय मिलेंगे।
व्यापक रूप में हम निष्कर्ष निकाल सकते हैं कि यदि समुच्चय M में n अवयव हैं, तो इस समुच्चय M के सभी उपसमुच्चयों की संख्या लंबाई n वाले सभी अलग-अलग द्विआधारी सदिशों की संख्या के बराबर है, और यह बराबर है
2n या n2: क्या कोई फ़र्क है? 🤷♂
अतः n संख्याओं वाले समुच्चय से 2n अलग-अलग उपसमुच्चय बन सकते हैं। हमारे उदाहरण में n = 12 संख्याएँ हैं, इसलिए हमें 212 अलग-अलग संचय जाँचने होंगे, यानी 4,096 संचय। हम कहेंगे कि इस समस्या की जटिलता 2n है, यानी चरघातांकी जटिलता, क्योंकि यह चरघातांकी फलन से व्यक्त होती है।
ध्यान दीजिए कि पिछली समस्या की जटिलता n2 थी, जबकि इसकी जटिलता 2n है। दोनों काफ़ी मिलते-जुलते दिखते हैं, है न? पर घातांक के अचर होने और उसकी जगह चर n होने में बड़ा अंतर है। ध्यान दीजिए कि n = 4 के लिए हमें मिलता है
ठीक है, अभी तक दोनों बराबर हैं। और यदि n = 10 हो?
अरे, चरघातांकी फलन अचानक उछल गया और द्विघाती फलन से लगभग दस गुना बड़ा हो गया। n = 20 के लिए क्या मिलेगा?
n = 20 के लिए चरघातांकी जटिलता का मान द्विघाती जटिलता से लगभग 2600 गुना अधिक है। इसलिए हम देखते हैं कि चरघातांकी फलन द्विघात फलन से कहीं तेज़ी से बढ़ता है। इसे तब याद कीजिए, जब फिर कोई महामारी आए जो जनसंख्या में चरघातांकी गति से फैले।
अतः यदि मैं आपके सामने बीस पर्चियाँ डालूँ, तो आपको 10,48,576 संचय जाँचने होंगे। यह काफ़ी अधिक है।
परिणाम की सत्यता की जाँच कैसे करें?
यह सत्यापित करने में मुझे कितना समय लगेगा कि परिणाम वाले संख्याओं के समूह का योग सचमुच 0 है? यह काफ़ी जल्दी होगा: मैं बस संख्याओं का यह एक समूह जोड़ूँगा। यदि इसका योग 0 हो, तो आपने पर्चियों का सही समूह ढूँढ़ा है, और यदि योग कुछ और हो, तो गलत।
फिर से हम देखते हैं कि परिणाम की जाँच करना उसे ढूँढ़ने से कहीं अधिक आसान है।
समस्या 4: यात्रा विक्रेता समस्या
यात्रा विक्रेता समस्या (travelling salesman problem) सबसे प्रसिद्ध एल्गोरिद्मिक समस्याओं में से एक है। मोटे तौर पर कहें तो एक यात्रा विक्रेता है, जो बारिश बेचता है। अपनी रोज़ी-रोटी कमाने के लिए इस विक्रेता को बहुत यात्रा करनी पड़ती है। इसलिए उसने तय किया कि वह भारत के 14 बड़े शहरों में से हर एक में जाएगा। वह कुछ भी बर्बाद नहीं करना चाहता, इसलिए उसने तय किया कि वह सबसे छोटा संभव मार्ग ढूँढ़ेगा, जो उसे इन सभी शहरों से होकर ले जाए। और हमारा काम ऐसा सबसे छोटा मार्ग ढूँढ़ना है।
यह सबसे छोटा मार्ग हम कैसे ढूँढ़ सकते हैं? सभी विकल्प आज़माकर।
हम इसे सरल बना सकते हैं। मान लीजिए कि किन्हीं भी दो शहरों के बीच एक ही सबसे छोटा रास्ता है। सभी शहरों से होकर जाने वाला सबसे छोटा मार्ग हम कैसे ढूँढ़ें? शहर 14 हैं। इसलिए शुरुआत करने के लिए हमारे पास 14 विकल्प हैं। मान लीजिए हमने पटना से शुरुआत की!!! पटना से हम कहाँ जा सकते हैं? सैद्धांतिक रूप से किसी भी दूसरे शहर में। यानी हम बचे हुए 13 शहरों में से चुन सकते हैं।
अभी से हम गिन सकते हैं कि पहले दो शहरों तक जाने के कुल 14 · 13 तरीके हैं: शुरुआत के लिए 14 विकल्प हैं और फिर बचे हुए 13 शहरों में से चुनना है।
दूसरे शहर में पहुँचकर हमें आगे बढ़ना है। दो शहरों में हम जा चुके हैं, इसलिए बचे हुए 12 शहरों में से किसी एक में जा सकते हैं। इस तरह पहले तीन शहरों तक जाने के कुल 14 · 13 · 12 तरीके हैं।
तीसरे शहर के बाद हमें बचे हुए 11 शहरों में से एक चुनना है, फिर बचे हुए 10 शहरों में से एक आदि।
सभी शहरों में जाने के बाद पता चलता है कि हमारे पास कुल
विकल्प थे। यह आपको क्रमगुणित की याद दिला सकता है, जिसे विस्मयादिबोधक चिह्न से दर्शाते हैं। इसलिए कह सकते हैं कि यह गुणनफल 14! के बराबर है:
अतः सभी 14 शहरों से होकर जाने वाले 14! मार्ग हैं। क्या यह बहुत है? काफ़ी, क्योंकि
व्यापक रूप में, यदि हम n शहरों के बीच सबसे छोटा मार्ग ढूँढ़ें, तो हमें n! अलग-अलग मार्ग आज़माने होंगे। इसलिए इस हल की जटिलता n! है।
हम कैसे सत्यापित करेंगे कि हमें सही परिणाम मिला है? यदि आप मुझसे कहें कि सबसे छोटा मार्ग भोपाल से पटना, फिर जयपुर आदि है, तो मैं कैसे जाँचूँ कि आप सच कह रहे हैं? बहुत मुश्किल से 🤷♂। इस मार्ग को देखकर मेरे पास यह आसानी से जाँचने का कोई तरीका नहीं है कि यही मार्ग सबसे छोटा है या नहीं। मुझे वास्तव में पूरी गणना फिर से करनी पड़ेगी। इसलिए परिणाम के सत्यापन की जटिलता भी n! है।
वर्ग P और NP
हमने चार समस्याएँ और उन्हें हल करने वाले एल्गोरिद्म देखे, और विश्लेषण किया कि हल ढूँढ़ना कितना जटिल है और इस हल की जाँच करना कितना जटिल है। इसे हम इस सारणी में संक्षेप में लिख सकते हैं:
| समस्या | हल की जटिलता | सत्यापन की जटिलता |
|---|---|---|
| सबसे छोटी संख्या | n | n |
| जोड़ी का गुणनफल | n2 | 1 |
| उपसमुच्चय का योग | 2n | n |
| यात्रा विक्रेता | n! | n! |
अब हम अपनी समस्याओं को दो समूहों में बाँटेंगे। पहला समूह उन समस्याओं का होगा, जिन्हें हल करना आसान है। ये वे समस्याएँ हैं, जिन्हें जटिलता n या n2 या n3 या n4 आदि से हल किया जा सकता है। n2 जैसे व्यंजकों को हम बहुपद (polynomial) कहते हैं, इसलिए समस्याओं के इस वर्ग को अक्षर P से दर्शाते हैं। अतः हम कहते हैं कि वर्ग P में वे समस्याएँ हैं, जिन्हें बहुपद समय में हल किया जा सकता है (यानी जिनकी जटिलता, जैसे, n2 या n7 है)। सामान्यतः ये वे समस्याएँ हैं, जिन्हें कमोबेश आसानी से हल किया जा सकता है।
वर्ग P में समस्या 1, सबसे छोटी संख्या ढूँढ़ना, आती है, क्योंकि उसके हल की जटिलता n है। और इसमें समस्या 2, जोड़ी का गुणनफल, भी आती है, क्योंकि उसके हल की जटिलता n2 है। दोनों बहुपद हैं।
दूसरा वर्ग NP है। इसमें वे समस्याएँ हैं, जिनका सत्यापन बहुपद समय में किया जा सकता है। इसलिए वर्ग NP में अंतिम को छोड़कर सभी समस्याएँ आती हैं। सबसे छोटा मार्ग ढूँढ़ने वाली यात्रा विक्रेता समस्या के हल का सत्यापन बहुपद समय में करने का कोई तरीका हम नहीं जानते। पहली तीन समस्याओं का सत्यापन बहुपद समय में किया जा सकता है।
यात्रा विक्रेता समस्या को बहुपद समय में न हल करना हम जानते हैं, न उसके हल का सत्यापन करना। इसलिए यात्रा विक्रेता समस्या के लिए हमें एक और वर्ग चाहिए होगा, जिसमें और भी कठिन समस्याएँ हों। ऐसा वर्ग है, पर अभी वह हमारे लिए रोचक नहीं है। (टिप्पणी: यदि प्रश्न केवल यह हो कि क्या दी गई लंबाई से छोटा कोई मार्ग है, तो सुझाए गए मार्ग की जाँच आसान है। समस्या का यह रूप वर्ग NP में है।)
स्पष्ट है कि वर्ग P वर्ग NP का उपसमुच्चय है, यानी जो भी समस्या वर्ग P में है, वह वर्ग NP में भी है। यह तर्कसंगत है: यदि हम किसी समस्या को बहुपद समय में हल कर सकते हैं, तो उसके परिणाम को भी बहुपद समय में सत्यापित कर सकते हैं।
P बनाम NP समस्या
क्या उलटा भी सत्य है? क्या वर्ग NP की हर समस्या वर्ग P में भी है? यानी, यदि किसी समस्या के परिणाम को बहुपद समय में सत्यापित करने का तरीका है, तो क्या ऐसा एल्गोरिद्म भी है जो उस समस्या को बहुपद समय में हल करे?
उदाहरण के लिए, हम जानते हैं कि समस्या 3, उपसमुच्चय का योग, के परिणाम को हम बहुपद समय में सत्यापित कर सकते हैं। पर इसे हल करने के लिए हमने जो एल्गोरिद्म इस्तेमाल किया, वह बहुपद नहीं है: इस एल्गोरिद्म की जटिलता चरघातांकी, 2n, है। पर क्या हम निश्चित रूप से जानते हैं कि इस समस्या के लिए बहुपद जटिलता वाला कोई एल्गोरिद्म नहीं है?
नहीं जानते!
हो सकता है कि हर उस समस्या के लिए, जिसे बहुपद समय में सत्यापित किया जा सकता है, ऐसा एल्गोरिद्म हो जो उसे बहुपद समय में हल करे। हम यह नहीं जानते। हम ऐसे एल्गोरिद्म का अस्तित्व सिद्ध नहीं कर सकते, पर उसके अस्तित्व का खंडन भी नहीं कर सकते।
यदि वर्ग NP की हर समस्या के लिए ऐसा एल्गोरिद्म होता, जो उसे बहुपद समय में हल करे, तो इसका अर्थ होता कि वर्ग NP वास्तव में वर्ग P के बराबर है। वर्ग P की सभी समस्याएँ वर्ग NP में होतीं और वर्ग NP की सभी समस्याएँ वर्ग P में होतीं, यानी दोनों वर्ग बराबर, एक ही होते।
अतः P बनाम NP समस्या यह प्रश्न है कि क्या वर्ग P वर्ग NP के समान है, या ये समस्याओं के दो अलग-अलग वर्ग हैं।
या तो P = NP है, या P ≠ NP है। यह कोई नहीं जानता, और यदि आप इसका पता लगा लें, तो आपको दस लाख डॉलर का पुरस्कार, अमर कीर्ति और शायद ट्यूरिंग पुरस्कार भी मिलेगा, जो कंप्यूटर वैज्ञानिकों के लिए नोबेल पुरस्कार जैसा है।
यदि P = NP हो, तो क्या होगा?
यदि P = NP सत्य हो, तो क्या होगा? यह कहना बहुत आसान नहीं है। हम जान जाएँगे कि वर्ग NP की सभी समस्याओं के लिए ऐसा एल्गोरिद्म है, जो उन्हें बहुपद समय में हल करे। उदाहरण के लिए, हमारी समस्या 3, उपसमुच्चय का योग, के लिए ऐसा एल्गोरिद्म है, जो उसे बहुपद समय में हल करे। पर इसमें तीन पेंच हैं:
- यह जानने से कि ऐसा एल्गोरिद्म है, यह नहीं निकलता कि हम उसे ढूँढ़ भी सकते हैं। हम बस जान जाएँगे कि हाँ, ऐसा एल्गोरिद्म है जो समस्या को बहुपद समय में हल करता है, पर हो सकता है कि अगले सौ साल तक हम उसे बना न पाएँ। यह कुछ वैसा ही है, जैसे सामान्य आपेक्षिकता सिद्धांत ने ब्लैक होल के अस्तित्व की भविष्यवाणी की, पर ब्लैक होल की पहली “तस्वीर” लेने में हमें उसके बाद भी कई दशक लग गए।
- बहुपद समय में काम करने वाले एल्गोरिद्म का अस्तित्व दुर्भाग्य से यह नहीं बताता कि वह तेज़ है। हमें ऐसा एल्गोरिद्म मिल सकता है, जिसकी जटिलता n100 हो। आख़िर व्यंजक n100 भी बहुपद है। जटिलताओं 2n और n100 की तुलना करें, तो पता चलता है कि जब तक n अपेक्षाकृत छोटा है, जटिलता 2n वाले एल्गोरिद्म को अब भी कम संक्रियाएँ चाहिए। उदाहरण के लिए, n = 20 के लिए 220 = 10,48,576 है, जबकि व्यंजक 20100 से लगभग 130 अंकों वाली संख्या मिलती है, जो 10,48,576 से 10 की 120 से भी अधिक घात गुना बड़ी है। इसलिए व्यवहार में हमारा बहुपद एल्गोरिद्म चरघातांकी एल्गोरिद्म से धीमा होगा। कम से कम तब तक, जब तक n अपेक्षाकृत छोटा है।
- यदि हम सचमुच बहुपद समय में काम करने वाला तेज़ एल्गोरिद्म ढूँढ़ लें, तो हम बहुत-सी समस्याएँ जल्दी और अधिक सटीकता से हल कर सकेंगे। यह निश्चित रूप से अच्छी ख़बर है, पर इसके नुकसान भी हैं। एक क्षेत्र ऐसा है, जो इस बात पर टिका है कि कुछ समस्याओं को हल करना कठिन है: क्रिप्टोग्राफ़ी (कूटलेखन)। ऐसा हो सकता है कि आज के सिफ़रों को तोड़ना कहीं अधिक आसान हो जाए।
बीच में एक बात: आप यहाँ तक पढ़ते आए हैं, इसलिए इनाम के रूप में बता देता हूँ कि समस्या 3 का हल 24 + 1 − 60 + 16 − 83 + 48 + 54 है।
यदि P ≠ NP हो, तो क्या होगा?
यदि यह सत्य हो कि समस्याओं के वर्ग P और NP अलग-अलग हैं, तो बहुत कुछ नहीं होगा, क्योंकि यह कमोबेश आज की स्थिति ही है। आज हमारे पास कोई ऐसा एल्गोरिद्म नहीं है, जो NP की किसी कठिन समस्या को बहुपद समय में हल करे। यदि कोई सिद्ध कर दे कि P ≠ NP, तो यह स्थिति हमेशा के लिए ऐसी ही रहेगी। इससे कहीं बड़ी सनसनी यह उपपत्ति होगी कि P = NP।
लोकप्रिय संस्कृति में
- द सिम्पसन्स (The Simpsons) के एक एपिसोड में होमर किसी वैकल्पिक दुनिया में पहुँच जाता है, जहाँ उसे दिखता है कि P = NP। इसे youtube.com पर देखा जा सकता है।
- फ़्यूचुरामा (Futurama) में इसके विपरीत दिखता है कि गोदाम में दो फ़ाइलें हैं, एक का नाम P और दूसरी का NP। इसे youtube.com पर देखा जा सकता है।
- अमेरिकी धारावाहिक Elementary के दूसरे सीज़न का दूसरा एपिसोड “Solve for X” एक ऐसे गणितज्ञ की हत्या के बारे में था, जिसने शायद P बनाम NP समस्या हल कर ली थी।