एनएल (जटिलता): Difference between revisions

From Vigyanwiki
(Created page with "{{unsolved|computer science|{{tmath|\mathsf{L \overset?{{=}} NL} }}}} कम्प्यूटेशनल जटिलता सिद्धांत में, एनए...")
 
No edit summary
 
(5 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{unsolved|computer science|{{tmath|\mathsf{L \overset?{{=}} NL} }}}}
{{unsolved|computer science|{{tmath|\mathsf{L \overset?{{=}} NL} }}}}
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, एनएल (नॉनडेटर्मिनिस्टिक लॉगरिदमिक-स्पेस) [[निर्णय समस्या]]ओं से युक्त [[जटिलता वर्ग]] है जिसे [[मेमोरी स्पेस (कम्प्यूटेशनल संसाधन)]] की लॉगरिदमिक मात्रा का उपयोग करके एक नॉनडेटर्मिनिस्टिक ट्यूरिंग मशीन द्वारा हल किया जा सकता है।
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, '''NL''' (गैर नियतात्मक लघुगणक-समष्टि) [[निर्णय समस्या|निर्णय समस्याओं]] से युक्त [[जटिलता वर्ग]] है जिसे [[मेमोरी स्पेस (कम्प्यूटेशनल संसाधन)|मेमोरी समष्टि (कम्प्यूटेशनल संसाधन)]] की लघुगणक मात्रा का उपयोग करके गैर नियतात्मक ट्यूरिंग मशीन द्वारा हल किया जा सकता है।


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


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


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


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


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


:<math>(x_1 \vee \neg x_3) \wedge (\neg x_2 \vee x_3) \wedge (\neg x_1 \vee \neg x_2)</math>
:<math>(x_1 \vee \neg x_3) \wedge (\neg x_2 \vee x_3) \wedge (\neg x_1 \vee \neg x_2)</math>
==संरोध==
अतः यह ज्ञात है कि '''{{sans-serif|NL}}''' {{sans-serif|[[P (complexity)|P]]}} में निहित है, चूँकि 2-संतुष्टि के लिए [[बहुपद-समय एल्गोरिथ्म|बहुपद-समय एल्गोरिदम]] है, परन्तु यह ज्ञात नहीं है कि '''{{sans-serif|NL {{=}} P}}''' या '''{{sans-serif|L {{=}} NL}}''' है या नहीं। यह ज्ञात है कि '''{{sans-serif|NL {{=}} co-NL}}''', जहाँ '''{{sans-serif|co-NL}}''' भाषाओं का वह वर्ग है जिसके [[पूरक (जटिलता)]] '''{{sans-serif|NL}}''' में हैं। इस प्रकार से यह परिणाम (इम्मरमैन-स्ज़ेलेपीसीसेनी प्रमेय) स्वतंत्र रूप से 1987 में [[नील इमरमैन]] और रोबर्ट स्ज़ेलेपीसीसेनी द्वारा खोजा गया था; इस कार्य के लिए उन्हें 1995 का गोडेल पुरस्कार मिला।


[[सर्किट जटिलता|परिपथ जटिलता]] में, '''{{sans-serif|NL}}''' को '''{{sans-serif|[[NC (complexity)|NC]]}}''' पदानुक्रम के भीतर रखा जा सकता है। पापादिमित्रिउ 1994, प्रमेय 16.1 में, इस प्रकार से हमारे निकट है:


==समाधान==
:'''<math>\mathsf{NC_1 \subseteq L \subseteq NL \subseteq NC_2}</math>'''.
ह ज्ञात है कि {{sans-serif|NL}} में समाहित है {{sans-serif|[[P (complexity)|P]]}}, चूँकि 2-संतुष्टि के लिए एक [[बहुपद-समय एल्गोरिथ्म]] है, लेकिन यह ज्ञात नहीं है कि क्या {{sans-serif|NL {{=}} P}} या कि {{sans-serif|L {{=}} NL}}. ह ज्ञात है कि {{sans-serif|NL {{=}} co-NL}}, कहाँ {{sans-serif|co-NL}} भाषाओं का वह वर्ग है जिसके [[पूरक (जटिलता)]] हैं {{sans-serif|NL}}. यह परिणाम (इम्मरमैन-स्ज़ेलेपीसीसेनी प्रमेय) स्वतंत्र रूप से 1987 में [[नील इमरमैन]] और रोबर्ट स्ज़ेलेपीसीसेनी द्वारा खोजा गया था; इस कार्य के लिए उन्हें 1995 का गोडेल पुरस्कार मिला।


[[सर्किट जटिलता]] में, {{sans-serif|NL}} के अंदर रखा जा सकता है {{sans-serif|[[NC (complexity)|NC]]}} पदानुक्रम। पापादिमित्रिउ 1994, प्रमेय 16.1 में, हमारे पास है:
अतः अधिक यथार्थ रूप से, {{sans-serif|NL}} {{sans-serif|[[AC (complexity)|AC<sup>1</sup>]]}} में निहित है। यह ज्ञात है कि '''{{sans-serif|NL}}''' '''{{sans-serif|[[ZPL (complexity)|ZPL]]}}''' के बराबर है, समस्याओं का वह वर्ग जिसे लघुगणकीय समष्टि और असीमित समय में यादृच्छिक एल्गोरिदम द्वारा बिना किसी त्रुटि के हल किया जा सकता है। यद्यपि, यह ज्ञात या माना नहीं जाता है कि यह '''{{sans-serif|[[RLP (complexity)|RLP]]}}''' या '''{{sans-serif|[[ZPLP (complexity)|ZPLP]]}}''' के बराबर है, '''{{sans-serif|RL}}''' और '''{{sans-serif|ZPL}}''' के बहुपद-समय प्रतिबंध, जिन्हें कुछ लेखक '''{{sans-serif|RL}}''' और '''{{sans-serif|ZPL}}''' के रूप में संदर्भित करते हैं।


:<math>\mathsf{NC_1 \subseteq L \subseteq NL \subseteq NC_2}</math>.
इस प्रकार से हम सैविच के प्रमेय का प्रयोग करके '''{{sans-serif|NL}}''' को नियतात्मक स्थान से जोड़ सकते हैं, जो हमें बताता है कि किसी भी गैर-नियतात्मक एल्गोरिदम को एक नियतात्मक मशीन द्वारा अधिकतम चतुर्भुज रूप से अधिक स्थान में अनुकरण किया जा सकता है। सैविच के प्रमेय से, हमारे निकट प्रत्यक्षतः यह है:
 
ज्यादा ठीक, {{sans-serif|NL}} में समाहित है {{sans-serif|[[AC (complexity)|AC<sup>1</sup>]]}}. ह ज्ञात है कि {{sans-serif|NL}} के बराबर है {{sans-serif|[[ZPL (complexity)|ZPL]]}}, बिना किसी त्रुटि के लघुगणकीय स्थान और असीमित समय में यादृच्छिक एल्गोरिदम द्वारा हल की जाने वाली समस्याओं का वर्ग। हालाँकि, इसके बराबर ज्ञात या विश्वास नहीं है {{sans-serif|[[RLP (complexity)|RLP]]}} या {{sans-serif|[[ZPLP (complexity)|ZPLP]]}}, बहुपद-समय प्रतिबंध {{sans-serif|RL}} और {{sans-serif|ZPL}}, जिसे कुछ लेखक कहते हैं {{sans-serif|RL}} और {{sans-serif|ZPL}}.
 
हम संबंधित कर सकते हैं {{sans-serif|NL}} सैविच के प्रमेय का उपयोग करके नियतात्मक स्थान के लिए, जो हमें बताता है कि किसी भी गैर-नियतात्मक एल्गोरिदम को एक नियतात्मक मशीन द्वारा अधिकतम चतुर्भुज रूप से अधिक स्थान में अनुकरण किया जा सकता है। सैविच के प्रमेय से, हमारे पास सीधे तौर पर यह है:


:<math>\mathsf{NL \subseteq SPACE}(\log^2 n) \ \ \ \  \text{equivalently, } \mathsf{NL \subseteq L}^2.</math>
:<math>\mathsf{NL \subseteq SPACE}(\log^2 n) \ \ \ \  \text{equivalently, } \mathsf{NL \subseteq L}^2.</math>
यह 1994 में ज्ञात सबसे मजबूत नियति-स्थान समावेशन था (पापादिमित्रिउ 1994 समस्या 16.4.10, सममित स्थान)। चूँकि बड़े अंतरिक्ष वर्ग द्विघात वृद्धि से प्रभावित नहीं होते हैं, इसलिए गैर-नियतात्मक और नियतात्मक वर्ग समान माने जाते हैं, इसलिए उदाहरण के लिए हमारे पास है {{sans-serif|[[PSPACE]] {{=}} [[NPSPACE]]}}.
अतः यह 1994 में ज्ञात सबसे दृढ नियति-समष्टि समावेशन था (पापादिमित्रिउ 1994 समस्या 16.4.10, सममित समष्टि)। चूँकि बड़े समष्टि वर्ग द्विघात वृद्धि से प्रभावित नहीं होते हैं, इसलिए गैर-नियतात्मक और नियतात्मक वर्ग समान माने जाते हैं, इसलिए उदाहरण के लिए हमारे निकट '''{{sans-serif|[[PSPACE]] {{=}} [[NPSPACE]]}}''' है।


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


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


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


एक सरल एल्गोरिदम है जो यह स्थापित करता है कि C = 'NL'। स्पष्ट रूप से C 'NL' में समाहित है, क्योंकि:
इस प्रकार से एक सरल एल्गोरिदम है जो यह स्थापित करता है कि C = ''''NL'''<nowiki/>'। स्पष्ट रूप से '''C 'NL'''' में निहित है, क्योंकि:
* यदि स्ट्रिंग भाषा में नहीं है, तो दोनों सभी गणना पथों को अस्वीकार कर देते हैं।
* यदि स्ट्रिंग भाषा में नहीं है, तो दोनों सभी गणना पथों को अस्वीकार कर देते हैं।
* यदि स्ट्रिंग भाषा में है, तो एक 'एनएल' एल्गोरिदम कम से कम एक गणना पथ को स्वीकार करता है और एक सी एल्गोरिदम अपने गणना पथों के कम से कम दो-तिहाई को स्वीकार करता है।
* यदि स्ट्रिंग भाषा में है, तो ''''NL'''<nowiki/>' एल्गोरिदम कम से कम गणना पथ को स्वीकार करता है और C एल्गोरिदम अपने गणना पथों के कम से कम दो-तिहाई को स्वीकार करता है।
यह दिखाने के लिए कि 'एनएल' सी में निहित है, हम बस एक 'एनएल' एल्गोरिदम लेते हैं और लंबाई एन का एक यादृच्छिक गणना पथ चुनते हैं, और इस 2 को निष्पादित करते हैं<sup>n</sup>बार. क्योंकि कोई भी गणना पथ लंबाई n से अधिक नहीं है, और क्योंकि 2 हैं<sup>n</sup> सभी गणना पथों में, हमारे पास स्वीकार करने वाले (एक स्थिरांक से नीचे घिरा हुआ) तक पहुंचने का एक अच्छा मौका है।
अतः यह दिखाने के लिए कि '<nowiki/>'''NL'''<nowiki/>' C में निहित है, हम मात्र ''''NL'''<nowiki/>' एल्गोरिदम लेते हैं और लंबाई n का यादृच्छिक गणना पथ चुनते हैं, और इस 2<sup>n</sup> बार निष्पादित करते हैं। क्योंकि कोई भी गणना पथ लंबाई n से अधिक नहीं है, और क्योंकि कुल मिलाकर 2<sup>n</sup> संगणना पथ हैं, हमारे निकट स्वीकार करने वाले (एक स्थिरांक द्वारा नीचे सीमित) तक पहुंचने का ठीक अवसर है।


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


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


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


===प्रमाणपत्र परिभाषा===
===प्रमाणपत्र परिभाषा===
एनएल को [[एनपी (जटिलता)]] जैसे वर्गों के अनुरूप, [[प्रमाणपत्र (जटिलता)]] द्वारा समतुल्य रूप से चित्रित किया जा सकता है। एक नियतात्मक लॉगरिदमिक-स्पेस बाउंडेड ट्यूरिंग मशीन पर विचार करें जिसमें एक अतिरिक्त रीड-ओनली-रीड-वन्स इनपुट टेप है। एक भाषा एनएल में तभी होती है जब ऐसी ट्यूरिंग मशीन अपने अतिरिक्त इनपुट टेप में प्रमाणपत्र के उचित विकल्प के लिए भाषा के किसी भी शब्द को स्वीकार करती है, और प्रमाणपत्र की परवाह किए बिना किसी भी शब्द को अस्वीकार कर देती है जो भाषा में नहीं है।<ref>{{cite book|last1=Arora|first1=Sanjeev|author1link = Sanjeev Arora|url=http://www.cs.princeton.edu/theory/complexity/|title=Complexity Theory: A Modern Approach|last2=Barak|first2=Boaz|author2link = Boaz Barak |date=2009|publisher=Cambridge University Press|isbn=978-0-521-42426-4|chapter=Definition 4.19}}</ref>
अतः '''NL''' को [[एनपी (जटिलता)|'''NP (जटिलता)''']] जैसे वर्गों के अनुरूप, [[प्रमाणपत्र (जटिलता)]] द्वारा समतुल्य रूप से चित्रित किया जा सकता है। नियतात्मक लघुगणक-समष्टि परिबद्ध ट्यूरिंग मशीन पर विचार करें जिसमें अतिरिक्त रीड-ओनली-रीड-वन्स इनपुट टेप है। इस प्रकार से भाषा '''NL''' में तभी होती है जब ऐसी ट्यूरिंग मशीन अपने अतिरिक्त इनपुट टेप में प्रमाणपत्र के उचित विकल्प के लिए भाषा के किसी भी शब्द को स्वीकार करती है, और प्रमाणपत्र को ध्यान दिए बिना किसी भी शब्द को अस्वीकार कर देती है जो भाषा में नहीं है।<ref>{{cite book|last1=Arora|first1=Sanjeev|author1link = Sanjeev Arora|url=http://www.cs.princeton.edu/theory/complexity/|title=Complexity Theory: A Modern Approach|last2=Barak|first2=Boaz|author2link = Boaz Barak |date=2009|publisher=Cambridge University Press|isbn=978-0-521-42426-4|chapter=Definition 4.19}}</ref>
केम से और अबुज़र याकार्यिलमाज़ ने साबित कर दिया है कि उपरोक्त कथन में नियतात्मक लॉगरिदमिक-स्पेस ट्यूरिंग मशीन को एक सीमाबद्ध-त्रुटि संभाव्य स्थिरांक-स्पेस ट्यूरिंग मशीन द्वारा प्रतिस्थापित किया जा सकता है जिसे केवल निरंतर संख्या में यादृच्छिक बिट्स का उपयोग करने की अनुमति है।<ref>A. C. Cem Say, Abuzer Yakaryılmaz, "Finite state verifiers with constant randomness," ''Logical Methods in Computer Science'', Vol. 10(3:6)2014, pp. 1-17.</ref>
 


अतः केम से और अबुज़र याकार्यिलमाज़ ने सिद्ध कर दिया है कि उपरोक्त कथन में नियतात्मक लघुगणक-समष्टि ट्यूरिंग मशीन को सीमाबद्ध-त्रुटि संभाव्य स्थिरांक-समष्टि ट्यूरिंग मशीन द्वारा प्रतिस्थापित किया जा सकता है जिसे मात्र निरंतर संख्या में यादृच्छिक बिट का उपयोग करने की अनुमति है।<ref>A. C. Cem Say, Abuzer Yakaryılmaz, "Finite state verifiers with constant randomness," ''Logical Methods in Computer Science'', Vol. 10(3:6)2014, pp. 1-17.</ref>
==वर्णनात्मक जटिलता==
==वर्णनात्मक जटिलता==
एनएल का एक सरल तार्किक लक्षण वर्णन है: इसमें सटीक रूप से वे भाषाएँ शामिल हैं जो एक अतिरिक्त [[ सकर्मक समापन ]] ऑपरेटर के साथ [[प्रथम-क्रम तर्क]] में व्यक्त की जा सकती हैं।
इस प्रकार से '''NL''' का सरल तार्किक लक्षण वर्णन है: इसमें यथार्थ रूप से वे भाषाएँ सम्मिलित हैं जो अतिरिक्त [[ सकर्मक समापन |सकर्मक संवरक]] संक्रियक के साथ [[प्रथम-क्रम तर्क]] में व्यक्त की जा सकती हैं।


== समापन गुण ==
== संवरक गुण ==
क्लास एनएल को ऑपरेशंस कॉम्प्लिमेंटेशन, यूनियन और इसलिए इंटरसेक्शन, कॉन्सटेनेशन#कॉन्टेनेशन_ऑफ_सेट्स_ऑफ_स्ट्रिंग्स और [[क्लेन स्टार]] के तहत बंद किया गया है।
इस प्रकार से कक्ष '''NL''' को संक्रियक पूरकन, संघ और इसलिए प्रतिच्छेदन, श्रृखंलाबद्धीकरण और [[क्लेन स्टार]] के अंतर्गत संवृत किया गया है।


==टिप्पणियाँ==
==टिप्पणियाँ==
{{Reflist}}
{{Reflist}}


==संदर्भ==
==संदर्भ==
Line 72: Line 68:
{{ComplexityClasses}}
{{ComplexityClasses}}


{{DEFAULTSORT:Nl (Complexity)}}[[Category: जटिलता वर्ग]]
{{DEFAULTSORT:Nl (Complexity)}}
 
 


[[Category: Machine Translated Page]]
[[Category:Collapse templates|Nl (Complexity)]]
[[Category:Created On 02/07/2023]]
[[Category:Created On 02/07/2023|Nl (Complexity)]]
[[Category:Machine Translated Page|Nl (Complexity)]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists|Nl (Complexity)]]
[[Category:Pages with script errors|Nl (Complexity)]]
[[Category:Sidebars with styles needing conversion|Nl (Complexity)]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready|Nl (Complexity)]]
[[Category:Templates generating microformats|Nl (Complexity)]]
[[Category:Templates that are not mobile friendly|Nl (Complexity)]]
[[Category:Templates using TemplateData|Nl (Complexity)]]
[[Category:Wikipedia metatemplates|Nl (Complexity)]]
[[Category:जटिलता वर्ग|Nl (Complexity)]]

Latest revision as of 19:15, 12 July 2023

Unsolved problem 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-संतुष्टि पूछती है, प्रस्तावात्मक तर्क सूत्र दिया गया है, जिसमें प्रत्येक खंड दो शाब्दिकों का विच्छेदन है, यदि कोई चर असाइनमेंट है जो सूत्र को सत्य बनाता है। इस प्रकार से उदाहरण उदाहरण, जहां इंगित नहीं करता है, हो सकता है:

संरोध

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

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

.

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

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

अतः यह 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 का यादृच्छिक गणना पथ चुनते हैं, और इस 2n बार निष्पादित करते हैं। क्योंकि कोई भी गणना पथ लंबाई n से अधिक नहीं है, और क्योंकि कुल मिलाकर 2n संगणना पथ हैं, हमारे निकट स्वीकार करने वाले (एक स्थिरांक द्वारा नीचे सीमित) तक पहुंचने का ठीक अवसर है।

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

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

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

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

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

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

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

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

संवरक गुण

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

टिप्पणियाँ

  1. Arora, Sanjeev; Barak, Boaz (2009). "Definition 4.19". Complexity Theory: A Modern Approach. Cambridge University Press. ISBN 978-0-521-42426-4.
  2. A. C. Cem Say, Abuzer Yakaryılmaz, "Finite state verifiers with constant randomness," Logical Methods in Computer Science, Vol. 10(3:6)2014, pp. 1-17.

संदर्भ