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

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) के रूप में परिभाषित किया जा सकता है।

जटिलता सिद्धांत में महत्वपूर्ण परिणाम हमें इस जटिलता वर्ग को अन्य वर्गों के साथ जोड़ने की अनुमति देते हैं, जो हमें इसमें सम्मिलित संसाधनों की सापेक्ष सामर्थ्य के विषय में बताते हैं। दूसरी ओर, कलन विधि के क्षेत्र में परिणाम हमें बताते हैं कि इस संसाधन से कौन सी समस्याएं हल की जा सकती हैं। अधिकांश जटिलता सिद्धांत की तरह, 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 है।

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

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

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

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

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

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

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

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

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

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

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

NL को एनपी (जटिलता) जैसे वर्गों के अनुरूप, प्रमाणपत्र (जटिलता) द्वारा समतुल्य रूप से चित्रित किया जा सकता है। नियतात्मक लघुगणक-समष्टि बाउंडेड ट्यूरिंग मशीन पर विचार करें जिसमें अतिरिक्त रीड-ओनली-रीड-वन्स इनपुट टेप है। भाषा 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).