L is different from NP
यह शोध पत्र दावा करता है कि वह यह सिद्ध करने का प्रमाण प्रदान करता है कि जटिलता वर्ग LOGSPACE (L), NP से भिन्न है।
मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें
कंप्यूटर विज्ञान के विशाल परिदृश्य में, दक्षता की सीमाओं के बारे में एक मौलिक प्रश्न विद्यमान है: किसी समस्या को हल करने के लिए एक मशीन को वास्तव में कितनी मेमोरी की आवश्यकता होती है? कल्पना कीजिए कि एक पुस्तकालय है जहाँ एक लाइब्रेरियन को एक विशिष्ट पुस्तक ढूँढनी है। यदि लाइब्रेरियन के पास कुछ पृष्ठ संख्याओं को नोट करने के लिए एक छोटी नोटबुक है, तो वे कार्य को तेज़ी से पूरा कर सकते हैं। यदि उनके पास पुस्तकालय के हर विवरण को संग्रहीत करने के लिए एक विशाल गोदाम है, तो कार्य बहुत सरल हो जाता है। जटिलता सिद्धांत (complexity theory) समस्याओं को इस आधार पर वर्गीकृत करता है कि उन्हें हल करने के लिए कंप्यूटर को कितनी "नोटबुक स्पेस" या मेमोरी की आवश्यकता होती है। एक श्रेणी, जिसे 'लॉगारिदमिक स्पेस' (logarithmic space) के रूप में जाना जाता है, उन समस्याओं का प्रतिनिधित्व करती है जिन्हें बहुत कम मेमोरी के साथ हल किया जा सकता है, जो इनपुट आकार के अंकों की संख्या के साथ ही बढ़ती है। दूसरी श्रेणी, जिसे 'नॉन-डिटरमिनिस्टिक पॉलीनोमियल टाइम' (nondeterministic polynomial time) के रूप में जाना जाता है, उन समस्याओं का प्रतिनिधित्व करती है जहाँ एक कंप्यूटर को समाधान तक पहुँचने के लिए अनुमान लगाने की आवश्यकता हो सकती है, जिसमें संभावित रूप से बहुत अधिक मेमोरी का उपयोग होता है। दशकों से, वैज्ञानिक आश्चर्य करते रहे हैं कि क्या ये दोनों श्रेणियाँ वास्तव में एक ही चीज़ हैं, या क्या कठिन समस्याओं के लिए छोटी नोटबुक मौलिक रूप से अपर्याप्त है।
'यूनिवर्सिडैड नैशनल डी कोलंबिया' के एक शोधकर्ता ने अब एक प्रमाण प्रस्तुत किया है जो तर्क देता है कि ये दोनों श्रेणियाँ वास्तव में भिन्न हैं। जे. एंड्रेस मोंटोया के नेतृत्व में किए गए इस कार्य में अनुमान या सिमुलेशन (simulation) पर निर्भर रहने के बजाय, इन दो गणनात्मक दुनियाओं को अलग करने के लिए एक कठोर गणितीय तर्क दिया गया है। प्रमाण का मुख्य आधार दो प्रकार की कम्प्यूटेशनल मशीनों के बीच एक चतुर तुलना है। एक तरफ बहुत सीमित मेमोरी वाली मशीनें हैं, जिन्हें लेखक ने एक विशिष्ट प्रकार के ऑटोमेटन (automaton) के रूप में मॉडल किया है, जो कुछ मार्करों या "पेबल्स" (pebbles) से लैस है जिन्हें वह अपनी स्थिति याद रखने के लिए एक टेप पर रख सकती है। दूसरी ओर, वे मशीनें हैं जो 'रियल-टाइम' (real-time) में कार्य करती हैं, यानी सूचना प्राप्त होते ही उसे तुरंत प्रोसेस करती हैं, बिना सोचने के लिए रुकने की विलासिता के। लेखक यह प्रदर्शित करते हैं कि रियल-टाइम मशीनें इतनी शक्तिशाली हैं कि वे उन समस्याओं को हल कर सकती हैं जिनमें निरंतर बढ़ते हुए पेबल्स की आवश्यकता होती है, जो सीमित-मेमोरी वाली मशीनों की क्षमता से कहीं अधिक है।
तर्क को समझने के लिए, सबसे पहले "पेबल पदानुक्रम" (pebble hierarchy) की अवधारणा को समझना आवश्यक है। कल्पना कीजिए कि एक मशीन जो एक लंबे कागज़ की पट्टी पर नेविगेट करने में मदद करने के लिए सीमित संख्या में मार्कर रख सकती है। एक मार्कर के साथ, मशीन समस्याओं के एक निश्चित सेट को हल कर सकती है। दो मार्करों के साथ, वह अधिक कठिन समस्याओं को हल कर सकती है। तीन के साथ, और भी अधिक। लेखक सिद्ध करते हैं कि बहुत कम मेमोरी के साथ हल की जाने वाली समस्याओं की श्रेणी, इन मार्करों की किसी भी सीमित संख्या के साथ हल की जाने वाली सभी समस्याओं के संग्रह के बिल्कुल बराबर है। यह कठिनाई की एक सीढ़ी बनाता है: जैसे-जैसे आप अधिक मार्कर जोड़ते हैं, आप ऊपर चढ़ते हैं और कठिन समस्याओं को हल करते हैं। लेखक फिर एक विशिष्ट, अत्यंत कठिन समस्या पेश करते हैं जिसे "हार्डेस्ट क्वासी-रियल-टाइम लैंग्वेज" (hardest quasi-real-time language) कहा जाता है। यह एक ऐसी समस्या है जिसे एक रियल-टाइम मशीन हल कर सकती है, और यह पूरे रियल-टाइम समस्याओं के वर्ग के लिए एक बेंचमार्क के रूप में कार्य करती है।
प्रमाण का सार यह दिखाने में निहित है कि यह सबसे कठिन रियल-टाइम समस्या मार्कर-आधारित मशीनों की सीढ़ी में इतनी ऊँची है कि इसे मार्करों की किसी भी सीमित संख्या द्वारा प्राप्त नहीं किया जा सकता है। लेखक तेजी से जटिल होती समस्याओं का एक क्रम निर्मित करते हैं, जिनमें से प्रत्येक पिछली वाली से अधिक कठिन है, और दिखाते हैं कि आपके द्वारा चुने गए मार्करों की किसी भी निश्चित संख्या के लिए, इस क्रम में एक ऐसी समस्या है जिसे वह मशीन हल नहीं कर सकती। चूँकि सबसे कठिन रियल-टाइम समस्या इस क्रम का हिस्सा है, इसलिए यह निष्कर्ष निकलता है कि मार्करों की कोई भी सीमित संख्या वाली मशीन इसे हल नहीं कर सकती। चूंकि सीमित-मेमोरी वाली मशीनें मार्करों की एक सीमित संख्या वाली मशीनों के समान हैं, इसलिए सबसे कठिन रियल-टाइम समस्या को सीमित मेमोरी के साथ हल नहीं किया जा सकता है।
इस निष्कर्ष का एक गहरा प्रभाव है: बहुत कम मेमोरी के साथ हल की जाने वाली समस्याओं की श्रेणी, रियल-टाइम मशीनों द्वारा हल की जाने वाली समस्याओं की श्रेणी से स्पष्ट रूप से छोटी है। चूँकि रियल-टाइम मशीनें उचित समय और मेमोरी के साथ हल की जा सकने वाली व्यापक श्रेणी का एक उपसमुच्चय (subset) हैं, यह सिद्ध करता है कि सूक्ष्म-मेमोरी वाली श्रेणी और बड़ी श्रेणी अलग हैं। लेखक स्पष्ट रूप से इस संभावना को खारिज करते हैं कि ये दोनों श्रेणियाँ एक ही हैं, और इस विचार को ध्वस्त करते हैं कि सभी कुशल गणनाओं के लिए एक छोटी नोटबुक पर्याप्त है। प्रमाण "एन्ट्रॉपी" (entropy) नामक एक तकनीक का उपयोग करता है, जो सूचना और अनिश्चितता का एक माप है, यह दिखाने के लिए कि इन कठिन समस्याओं को हल करने वाली मशीन की आंतरिक अवस्था (internal state) में उस जानकारी से अधिक जानकारी होनी चाहिए जो सीमित मार्करों वाली मशीन में समाहित हो सकती है।
लेख समाप्त करते हुए उल्लेख करता है कि यह पृथक्करण केवल विश्लेषण की गई विशिष्ट श्रेणियों के लिए ही सत्य नहीं है, बल्कि यह संकेत देता है कि अन्य प्रमुख जटिलता वर्गों (complexity classes) को भी अलग सिद्ध करने की दिशा में एक मार्ग प्रशस्त करता है। लेखक सुझाव देते हैं कि समान रणनीतियों का उपयोग यह दिखाने के लिए किया जा सकता है कि 'नॉन-डिटरमिनिस्टिक लॉगरिदमिक स्पेस' भी 'नॉन-डिटरमिनिस्टिक पॉलीनोमियल टाइम' से भिन्न है, और संभावित रूप से यह भी कि 'पॉलीनोमियल टाइम' भी 'नॉन-डिटरमिनिस्टिक पॉलीनोमियल टाइम' से अलग है। जबकि लेख 'लॉगारिदमिक स्पेस' और 'नॉन-डिटरमिनिस्टिक पॉलीनोमियल टाइम' के बीच अलगाव पर केंद्रित है, इसकी पद्धति—यह दिखाना कि समस्याओं का एक वर्ग मशीन क्षमताओं के पदानुक्रम में कितना "ऊँचा" है—कंप्यूटेशन की मौलिक सीमाओं को समझने के लिए एक नया और शक्तिशाली उपकरण प्रदान करती है। यह कार्य एक निर्णायक तर्क के रूप में खड़ा है कि कुछ समस्याएँ स्वाभाविक रूप से इतनी जटिल हैं कि उन्हें न्यूनतम मेमोरी के साथ हल नहीं किया जा सकता, चाहे एल्गोरिदम कितना भी चतुर क्यों न हो।
अपने क्षेत्र के पेपरों की भीड़ में उलझे हुए हैं?
आपके रिसर्च कीवर्ड से मेल खाने वाले सबसे नए और अलग सोच वाले पेपरों का रोज़ाना Digest पाएँ—तकनीकी सारांश के साथ, आपकी भाषा में।