एनएल (जटिलता)

Unsolved problem in computer science:

${\mathsf {L{\overset {?}{=}}NL}}$

(more unsolved problems in computer science)

कम्प्यूटेशनल जटिलता सिद्धांत में, NL (गैर नियतात्मक लघुगणक-समष्टि) निर्णय समस्याओं से युक्त जटिलता वर्ग है जिसे मेमोरी समष्टि (कम्प्यूटेशनल संसाधन) की लघुगणक मात्रा का उपयोग करके गैर नियतात्मक ट्यूरिंग मशीन द्वारा हल किया जा सकता है।

NL L (जटिलता) का सामान्यीकरण है, जो नियतात्मक ट्यूरिंग मशीन पर लघुगणक-समष्टि समस्याओं के लिए वर्ग है। चूँकि कोई भी नियतात्मक ट्यूरिंग मशीन भी गैर-नियतात्मक ट्यूरिंग मशीन है, हमारे निकट यह है कि L NL में निहित है।

NL को औपचारिक रूप से कम्प्यूटेशनल संसाधन गैर-नियतात्मक समष्टि (या एनएसपीएसीई) के संदर्भ में NL = NSPACE(log n) के रूप में परिभाषित किया जा सकता है।

जटिलता सिद्धांत में महत्वपूर्ण परिणाम हमें इस जटिलता वर्ग को अन्य वर्गों के साथ जोड़ने की अनुमति देते हैं, जो हमें इसमें सम्मिलित संसाधनों की सापेक्ष सामर्थ्य के विषय में बताते हैं। दूसरी ओर, कलन विधि के क्षेत्र में परिणाम हमें बताते हैं कि इस संसाधन से कौन C समस्याएं हल की जा सकती हैं। अधिकांश जटिलता सिद्धांत की तरह, NL के विषय में कई महत्वपूर्ण प्रश्न अभी भी विवृत समस्या हैं (कंप्यूटर विज्ञान में अनसुलझी समस्याएं देखें)।

नीचे दी गई संभाव्य परिभाषा के कारण कभी-कभी NL को RL के रूप में संदर्भित किया जाता है; यद्यपि, इस नाम का उपयोग प्रायः RL (जटिलता) को संदर्भित करने के लिए किया जाता है, जिसे NL के बराबर नहीं जाना जाता है।

NL-पूर्ण समस्याएं

लॉग-समष्टि कटौती के अंतर्गत कई समस्याओं को NL-पूर्ण माना जाता है, जिनमें ST-अनुयोजकता और 2-संतुष्टि सम्मिलित है। ST-अनुयोजकता निर्देशित आरेख में नोड्स S और T के लिए पूछती है कि क्या T S से पहुंच योग्य है। 2-संतुष्टि पूछती है, प्रस्तावात्मक तर्क सूत्र दिया गया है, जिसमें प्रत्येक खंड दो शाब्दिकों का विच्छेदन है, यदि कोई चर असाइनमेंट है जो सूत्र को सत्य बनाता है। उदाहरण उदाहरण, जहां $\neg$ इंगित नहीं करता है, हो सकता है:

$(x_{1}\vee \neg x_{3})\wedge (\neg x_{2}\vee x_{3})\wedge (\neg x_{1}\vee \neg x_{2})$

संरोध

यह ज्ञात है कि NL P में निहित है, चूँकि 2-संतुष्टि के लिए बहुपद-समय एल्गोरिदम है, परन्तु यह ज्ञात नहीं है कि NL = P या L = NL है या नहीं। यह ज्ञात है कि NL = co-NL, जहाँ co-NL भाषाओं का वह वर्ग है जिसके पूरक (जटिलता) NL में हैं। यह परिणाम (इम्मरमैन-स्ज़ेलेपीसीसेनी प्रमेय) स्वतंत्र रूप से 1987 में नील इमरमैन और रोबर्ट स्ज़ेलेपीसीसेनी द्वारा खोजा गया था; इस कार्य के लिए उन्हें 1995 का गोडेल पुरस्कार मिला।

परिपथ जटिलता में, NL को NC पदानुक्रम के भीतर रखा जा सकता है। पापादिमित्रिउ 1994, प्रमेय 16.1 में, हमारे निकट है:

${\mathsf {NC_{1}\subseteq L\subseteq NL\subseteq NC_{2}}}$.

अधिक यथार्थ रूप से, NL AC¹ में निहित है। यह ज्ञात है कि NL ZPL के बराबर है, समस्याओं का वह वर्ग जिसे लघुगणकीय समष्टि और असीमित समय में यादृच्छिक एल्गोरिदम द्वारा बिना किसी त्रुटि के हल किया जा सकता है। यद्यपि, यह ज्ञात या माना नहीं जाता है कि यह RLP या ZPLP के बराबर है, RL और ZPL के बहुपद-समय प्रतिबंध, जिन्हें कुछ लेखक RL और ZPL के रूप में संदर्भित करते हैं।

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

${\mathsf {NL\subseteq SPACE}}(\log ^{2}n)\ \ \ \ {\text{equivalently, }}{\mathsf {NL\subseteq L}}^{2}.$

यह 1994 में ज्ञात सबसे दृढ नियति-समष्टि समावेशन था (पापादिमित्रिउ 1994 समस्या 16.4.10, सममित समष्टि)। चूँकि बड़े समष्टि वर्ग द्विघात वृद्धि से प्रभावित नहीं होते हैं, इसलिए गैर-नियतात्मक और नियतात्मक वर्ग समान माने जाते हैं, इसलिए उदाहरण के लिए हमारे निकट PSPACE = NPSPACE है।

वैकल्पिक परिभाषाएँ

संभाव्य परिभाषा

मान लीजिए C संभाव्य ट्यूरिंग मशीनों के साथ लघुगणक समष्टि में हल करने योग्य निर्णय समस्याओं की जटिलता वर्ग है जो कभी भी अनुचित विधि से स्वीकार नहीं करती है परन्तु 1/3 से भी कम समय में अनुचित विधि से अस्वीकार करने की अनुमति दी जाती है; इसे एकओर त्रुटि कहा जाता है। स्थिरांक 1/3 यादृच्छिक है; 0 ≤ x < 1/2 वाला कोई भी x पर्याप्त होगा।

यह पता चला है कि C = 'NL'। ध्यान दें कि C, अपने नियतात्मक समकक्ष 'L (जटिलता)' के विपरीत, बहुपद समय तक सीमित नहीं है, क्योंकि यद्यपि इसमें बहुपद संख्या में कॉन्फ़िगरेशन हैं, यह अनंत पाश से बचने के लिए यादृच्छिकता का उपयोग कर सकता है। यदि हम इसे बहुपद समय तक सीमित करते हैं, तो हमें वर्ग 'RL (जटिलता)' मिलता है, जो 'NL' में निहित है परन्तु ज्ञात नहीं है या इसके बराबर नहीं माना जाता है।

एक सरल एल्गोरिदम है जो यह स्थापित करता है कि C = 'NL'। स्पष्ट रूप से C 'NL' में निहित है, क्योंकि:

• यदि स्ट्रिंग भाषा में नहीं है, तो दोनों सभी गणना पथों को अस्वीकार कर देते हैं।
• यदि स्ट्रिंग भाषा में है, तो 'NL' एल्गोरिदम कम से कम गणना पथ को स्वीकार करता है और C एल्गोरिदम अपने गणना पथों के कम से कम दो-तिहाई को स्वीकार करता है।

यह दिखाने के लिए कि 'NL' C में निहित है, हम मात्र 'NL' एल्गोरिदम लेते हैं और लंबाई n का यादृच्छिक गणना पथ चुनते हैं, और इस 2ⁿ बार निष्पादित करते हैं। क्योंकि कोई भी गणना पथ लंबाई n से अधिक नहीं है, और क्योंकि कुल मिलाकर 2ⁿ संगणना पथ हैं, हमारे निकट स्वीकार करने वाले (एक स्थिरांक द्वारा नीचे सीमित) तक पहुंचने का ठीक अवसर है।

एकमात्र समस्या यह है कि हमारे निकट 2ⁿ तक जाने वाले बाइनरी काउंटर के लिए लॉग समष्टि में स्थान नहीं है। इससे मुक्ति पाने के लिए हम इसे यादृच्छिक काउंटर से बदल देते हैं, जो मात्र n सिक्कों को उछालता है और रुक जाता है और यदि वे सभी शीर्ष पर गिरते हैं तो अस्वीकार कर देता है। चूँकि इस घटना की प्रायिकता 2⁻ⁿ है, हम रुकने से पहले औसतन 2ⁿ चरण उठाने की अपेक्षा करते हैं। इसे मात्र पंक्ति में देखे गए शीर्षों की संख्या का कुल योग रखना होगा, जिसे वह लॉग समष्टि में गिन सकता है।

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

इस प्रकार, जब हम मात्र समष्टि को देखते हैं, तो ऐसा लगता है कि यादृच्छिकीकरण और गैर-नियतिवाद समान रूप से शक्तिशाली हैं।

प्रमाणपत्र परिभाषा

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

केम से और अबुज़र याकार्यिलमाज़ ने सिद्ध कर दिया है कि उपरोक्त कथन में नियतात्मक लघुगणक-समष्टि ट्यूरिंग मशीन को सीमाबद्ध-त्रुटि संभाव्य स्थिरांक-समष्टि ट्यूरिंग मशीन द्वारा प्रतिस्थापित किया जा सकता है जिसे मात्र निरंतर संख्या में यादृच्छिक बिट का उपयोग करने की अनुमति है।

वर्णनात्मक जटिलता

NL का सरल तार्किक लक्षण वर्णन है: इसमें यथार्थ रूप से वे भाषाएँ सम्मिलित हैं जो अतिरिक्त सकर्मक समापन संक्रियक के साथ प्रथम-क्रम तर्क में व्यक्त की जा सकती हैं।

समापन गुण

कक्ष NL को संक्रियक पूरकन, संघ और इसलिए प्रतिच्छेदन, श्रृखंलाबद्धीकरण और क्लेन स्टार के अंतर्गत संवृत किया गया है।

संदर्भ

• Complexity Zoo: NL
• Papadimitriou, C. (1994). "Chapter 16: Logarithmic Space". Computational Complexity. Addison-Wesley. ISBN 0-201-53082-1.
• Michael Sipser (27 June 1997). "Sections 8.4–8.6: The Classes L and NL, NL-completeness, NL equals coNL". Introduction to the Theory of Computation. PWS Publishing. pp. 294–302. ISBN 0-534-94728-X.
• Introduction to Complexity Theory: Lecture 7. Oded Goldreich. Proposition 6.1. Our C is what Goldreich calls badRSPACE(log n).