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

Unsolved problem in computer science:

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

(more unsolved problems in computer science)

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

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

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

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

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

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

लॉग-स्पेस कटौती के तहत कई समस्याओं को एनएल-पूर्ण माना जाता है, जिनमें एसटी-कनेक्टिविटी और 2-संतुष्टि शामिल है। एसटी-कनेक्टिविटी एक निर्देशित ग्राफ में नोड्स एस और टी के लिए पूछती है कि क्या टी एस से पहुंच योग्य है। 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 पर्याप्त होगा।

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

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

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

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

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

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

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

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

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

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

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

समापन गुण

क्लास एनएल को ऑपरेशंस कॉम्प्लिमेंटेशन, यूनियन और इसलिए इंटरसेक्शन, कॉन्सटेनेशन#कॉन्टेनेशन_ऑफ_सेट्स_ऑफ_स्ट्रिंग्स और क्लेन स्टार के तहत बंद किया गया है।

संदर्भ

• 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).