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

From Vigyanwiki
(Created page with "{{short description|Complexity class (logarithmic space)}} {{redirect-distinguish|Logspace|Logscale}} कम्प्यूटेशनल जटिलता सिद्ध...")
 
No edit summary
Line 1: Line 1:
{{short description|Complexity class (logarithmic space)}}
{{short description|Complexity class (logarithmic space)}}
{{redirect-distinguish|Logspace|Logscale}}
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, एल (जिसे एलएसपीएसीई या डीएलओजीस्पेस के रूप में भी जाना जाता है) [[जटिलता वर्ग]] है जिसमें [[निर्णय समस्या]]एं सम्मिलित हैं जिन्हें लिखने योग्य [[मेमोरी स्पेस (कम्प्यूटेशनल संसाधन)]] की लॉगरिदमिक मात्रा का उपयोग करके [[नियतात्मक ट्यूरिंग मशीन]] द्वारा हल किया जा सकता है।<ref name="sip295">{{harvtxt|Sipser|1997}}, Definition&nbsp;8.12, p.&nbsp;295.</ref><ref name="gj-177">{{harvtxt|Garey|Johnson|1979}}, p.&nbsp;177.</ref> औपचारिक रूप से, ट्यूरिंग मशीन में दो टेप होते हैं, जिनमें से एक इनपुट को एनकोड करता है और इसे केवल पढ़ा जा सकता है,<ref>On a read/write input tape, a linear amount of memory could be obtained by packing of symbols (as in the proof of the [[linear speedup theorem]]), thus evading the logspace contraint.</ref> जबकि दूसरे टेप का आकार लघुगणकीय है किन्तु इसे पढ़ा भी जा सकता है और लिखा भी जा सकता है। लॉगरिदमिक स्थान इनपुट में [[ सूचक (कंप्यूटर प्रोग्रामिंग) |सूचक (कंप्यूटर प्रोग्रामिंग)]] की निरंतर संख्या रखने के लिए पर्याप्त है<ref name="sip295"/>और बूलियन फ़्लैग की एक लघुगणकीय संख्या और अनेक बुनियादी लॉगस्पेस एल्गोरिदम इस तरह से मेमोरी का उपयोग करते हैं।
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, एल (जिसे एलएसपीएसीई या डीएलओजीस्पेस के रूप में भी जाना जाता है) [[जटिलता वर्ग]] है जिसमें [[निर्णय समस्या]]एं शामिल हैं जिन्हें लिखने योग्य [[मेमोरी स्पेस (कम्प्यूटेशनल संसाधन)]] की लॉगरिदमिक मात्रा का उपयोग करके [[नियतात्मक ट्यूरिंग मशीन]] द्वारा हल किया जा सकता है।<ref name="sip295">{{harvtxt|Sipser|1997}}, Definition&nbsp;8.12, p.&nbsp;295.</ref><ref name="gj-177">{{harvtxt|Garey|Johnson|1979}}, p.&nbsp;177.</ref> औपचारिक रूप से, ट्यूरिंग मशीन में दो टेप होते हैं, जिनमें से एक इनपुट को एनकोड करता है और इसे केवल पढ़ा जा सकता है,<ref>On a read/write input tape, a linear amount of memory could be obtained by packing of symbols (as in the proof of the [[linear speedup theorem]]), thus evading the logspace contraint.</ref> जबकि दूसरे टेप का आकार लघुगणकीय है लेकिन इसे पढ़ा भी जा सकता है और लिखा भी जा सकता है। लॉगरिदमिक स्थान इनपुट में [[ सूचक (कंप्यूटर प्रोग्रामिंग) ]] की निरंतर संख्या रखने के लिए पर्याप्त है<ref name="sip295"/>और बूलियन फ़्लैग की एक लघुगणकीय संख्या, और कई बुनियादी लॉगस्पेस एल्गोरिदम इस तरह से मेमोरी का उपयोग करते हैं।


==संपूर्ण समस्याएँ और तार्किक लक्षण वर्णन==
==संपूर्ण समस्याएँ और तार्किक लक्षण वर्णन==
एल में प्रत्येक गैर-तुच्छ समस्या लॉग-स्पेस कटौती के तहत [[पूर्ण (जटिलता)]] है,<ref>See {{harvtxt|Garey|Johnson|1979}}, Theorem 7.13 (claim 2), p.&nbsp;179.</ref> इसलिए एल-पूर्णता की सार्थक धारणाओं की पहचान करने के लिए कमजोर कटौती की आवश्यकता होती है, सबसे आम है [[एफओ (जटिलता)]]|प्रथम-क्रम प्रथम-क्रम कमी।
एल में प्रत्येक गैर-तुच्छ समस्या लॉग-स्पेस कटौती के तहत [[पूर्ण (जटिलता)]] है,<ref>See {{harvtxt|Garey|Johnson|1979}}, Theorem 7.13 (claim 2), p.&nbsp;179.</ref> इसलिए एल-पूर्णता की सार्थक धारणाओं की पहचान करने के लिए कमजोर कटौती की आवश्यकता होती है, सबसे सामान्य है [[एफओ (जटिलता)]]|प्रथम-क्रम प्रथम-क्रम कमी।


[[ओमर रींगोल्ड]] द्वारा 2004 के एक परिणाम से पता चलता है कि [[यूएसटीसीओएन]], किसी दिए गए [[अप्रत्यक्ष ग्राफ]]़ में दो शीर्षों के बीच एक पथ मौजूद है या नहीं, की समस्या एल में है, जो दर्शाता है कि एल = [[एसएल (जटिलता)]], क्योंकि यूएसटीसीओएन एसएल-पूर्ण है।<ref>{{cite conference
[[ओमर रींगोल्ड]] द्वारा 2004 के एक परिणाम से पता चलता है कि [[यूएसटीसीओएन]] किसी दिए गए [[अप्रत्यक्ष ग्राफ]]़ में दो शीर्षों के मध्य एक पथ उपस्थित है या नहीं की समस्या एल में है जो दर्शाता है कि एल = [[एसएल (जटिलता)]], क्योंकि यूएसटीसीओएन एसएल-पूर्ण है।<ref>{{cite conference
  | last = Reingold | first = Omer
  | last = Reingold | first = Omer
  | title = Undirected ST-connectivity in log-space
  | title = Undirected ST-connectivity in log-space
Line 17: Line 16:
  | url = http://www.wisdom.weizmann.ac.il/~reingold/publications/sl.ps
  | url = http://www.wisdom.weizmann.ac.il/~reingold/publications/sl.ps
  | year = 2005}}</ref>
  | year = 2005}}</ref>
इसका एक परिणाम एल का एक सरल तार्किक लक्षण वर्णन है: इसमें एक अतिरिक्त कम्यूटिव [[ सकर्मक समापन ]] ऑपरेटर के साथ [[प्रथम-क्रम तर्क]] में व्यक्त की जाने वाली सटीक भाषाएं शामिल हैं ([[ग्राफ सिद्धांत]] के संदर्भ में, यह प्रत्येक जुड़े घटक (ग्राफ सिद्धांत) को एक क्लिक (ग्राफ) में बदल देता है लिखित))। यह परिणाम डेटाबेस क्वेरी भाषाओं पर लागू होता है: किसी क्वेरी की ''डेटा जटिलता'' को डेटा आकार को परिवर्तनीय इनपुट के रूप में मानते हुए एक निश्चित क्वेरी का उत्तर देने की जटिलता के रूप में परिभाषित किया गया है। इस उपाय के लिए, [[संबंधपरक बीजगणित]] में उदाहरण के लिए व्यक्त की गई संपूर्ण जानकारी ([[शून्य (एसक्यूएल)]] की कोई धारणा नहीं) के साथ संबंधपरक डेटाबेस के विरुद्ध प्रश्न एल में हैं।
 
इसका एक परिणाम एल का एक सरल तार्किक लक्षण वर्णन है: इसमें एक अतिरिक्त कम्यूटिव [[ सकर्मक समापन |सकर्मक समापन]] ऑपरेटर के साथ [[प्रथम-क्रम तर्क]] में व्यक्त की जाने वाली सटीक भाषाएं सम्मिलित हैं ([[ग्राफ सिद्धांत]] के संदर्भ में यह प्रत्येक जुड़े घटक (ग्राफ सिद्धांत) को एक क्लिक (ग्राफ) में बदल देता है लिखित))। यह परिणाम डेटाबेस क्वेरी भाषाओं पर लागू होता है: किसी क्वेरी की ''डेटा जटिलता'' को डेटा आकार को परिवर्तनीय इनपुट के रूप में मानते हुए एक निश्चित क्वेरी का उत्तर देने की जटिलता के रूप में परिभाषित किया गया है। इस उपाय के लिए [[संबंधपरक बीजगणित]] में उदाहरण के लिए व्यक्त की गई संपूर्ण जानकारी ([[शून्य (एसक्यूएल)]] की कोई धारणा नहीं) के साथ संबंधपरक डेटाबेस के विरुद्ध प्रश्न एल में हैं।


==संबंधित जटिलता वर्ग==
==संबंधित जटिलता वर्ग==


एल [[एनएल (जटिलता)]] का एक उपवर्ग है, जो एक [[गैर-नियतात्मक ट्यूरिंग मशीन]] पर लघुगणकीय स्थान में निर्णय लेने योग्य भाषाओं का वर्ग है। एनएल में एक समस्या को गैर-नियतात्मक मशीन के राज्यों और राज्य संक्रमणों का प्रतिनिधित्व करने वाले एक [[निर्देशित ग्राफ]] में पहुंच की समस्या में तब्दील किया जा सकता है, और लॉगरिदमिक स्पेस बाउंड का तात्पर्य है कि इस ग्राफ में कोने और किनारों की बहुपद संख्या है, जिससे यह एनएल का अनुसरण करता है नियतात्मक बहुपद समय में हल करने योग्य समस्याओं की जटिलता वर्ग [[पी (जटिलता)]] में निहित है।<ref>{{harvtxt|Sipser|1997}}, Corollary&nbsp;8.21, p.&nbsp;299.</ref> इस प्रकार L ⊆ NL ⊆ ⊆ P. L को P में शामिल करने को और अधिक सीधे तौर पर सिद्ध किया जा सकता है: ''O'' (log ''n'') स्पेस का उपयोग करने वाला एक निर्णायक 2 से अधिक का उपयोग नहीं कर सकता है<sup>ओ(लॉग एन)</sup>=एन<sup>O(1)</sup> समय, क्योंकि यह संभावित कॉन्फ़िगरेशन की कुल संख्या है।
एल [[एनएल (जटिलता)]] का एक उपवर्ग है, जो एक [[गैर-नियतात्मक ट्यूरिंग मशीन]] पर लघुगणकीय स्थान में निर्णय लेने योग्य भाषाओं का वर्ग है। एनएल में एक समस्या को गैर-नियतात्मक मशीन के राज्यों और राज्य संक्रमणों का प्रतिनिधित्व करने वाले एक [[निर्देशित ग्राफ]] में पहुंच की समस्या में तब्दील किया जा सकता है, और लॉगरिदमिक स्पेस बाउंड का तात्पर्य है कि इस ग्राफ में कोने और किनारों की बहुपद संख्या है, जिससे यह एनएल का अनुसरण करता है नियतात्मक बहुपद समय में हल करने योग्य समस्याओं की जटिलता वर्ग [[पी (जटिलता)]] में निहित है।<ref>{{harvtxt|Sipser|1997}}, Corollary&nbsp;8.21, p.&nbsp;299.</ref> इस प्रकार L ⊆ NL ⊆ ⊆ P. L को P में सम्मिलित करने को और अधिक सीधे तौर पर सिद्ध किया जा सकता है: ''O'' (log ''n'') स्पेस का उपयोग करने वाला एक निर्णायक 2 से अधिक का उपयोग नहीं कर सकता है<sup>ओ(लॉग एन)</sup>=एन<sup>O(1)</sup> समय, क्योंकि यह संभावित कॉन्फ़िगरेशन की कुल संख्या है।


'एल' आगे वर्ग '[[एनसी (जटिलता)]]' से निम्नलिखित तरीके से संबंधित है:
'एल' आगे वर्ग '[[एनसी (जटिलता)]]' से निम्नलिखित तरीके से संबंधित है:
Line 27: Line 27:
शब्दों में, बहुपद संख्या O(n) वाला एक समानांतर कंप्यूटर C दिया गया है<sup>k</sup>) कुछ स्थिर k के लिए प्रोसेसर, कोई भी समस्या जिसे C पर O(लॉग एन) समय में हल किया जा सकता है, वह 'L' में है, और 'L' में कोई भी समस्या O(लॉग) समय में हल की जा सकती है<sup>2</sup> n) C पर समय।
शब्दों में, बहुपद संख्या O(n) वाला एक समानांतर कंप्यूटर C दिया गया है<sup>k</sup>) कुछ स्थिर k के लिए प्रोसेसर, कोई भी समस्या जिसे C पर O(लॉग एन) समय में हल किया जा सकता है, वह 'L' में है, और 'L' में कोई भी समस्या O(लॉग) समय में हल की जा सकती है<sup>2</sup> n) C पर समय।


{{Unsolved|computer science|{{tmath|1= \mathsf{L} \overset{?}{=} \mathsf{P} }}}}
कंप्यूटर विज्ञान में अनसुलझी समस्याओं की महत्वपूर्ण सूची में यह सम्मिलित है कि क्या एल=पी,<ref name="gj-177"/>और क्या एल = एनएल।<ref>{{harvtxt|Sipser|1997}}, p.&nbsp;297; {{harvtxt|Garey|Johnson|1979}}, p.&nbsp;180.</ref> यह भी ज्ञात नहीं है कि एल = [[एनपी (जटिलता)]]।<ref>{{Cite web|url=https://cs.stackexchange.com/questions/103073/is-it-possible-that-l-np|title = Complexity theory - is it possible that $L=NP$?}}</ref>
 
फलन समस्याओं का संबंधित वर्ग FL (जटिलता) है। FL का उपयोग अधिकांशतः लॉगस्पेस कटौती को परिभाषित करने के लिए किया जाता है।
कंप्यूटर विज्ञान में अनसुलझी समस्याओं की महत्वपूर्ण सूची में यह शामिल है कि क्या एल=पी,<ref name="gj-177"/>और क्या एल = एनएल।<ref>{{harvtxt|Sipser|1997}}, p.&nbsp;297; {{harvtxt|Garey|Johnson|1979}}, p.&nbsp;180.</ref> यह भी ज्ञात नहीं है कि एल = [[एनपी (जटिलता)]]।<ref>{{Cite web|url=https://cs.stackexchange.com/questions/103073/is-it-possible-that-l-np|title = Complexity theory - is it possible that $L=NP$?}}</ref>
फ़ंक्शन समस्याओं का संबंधित वर्ग FL (जटिलता) है। FL का उपयोग अक्सर लॉगस्पेस कटौती को परिभाषित करने के लिए किया जाता है।


==अतिरिक्त गुण==
==अतिरिक्त गुण==
एल अपने लिए [[कम (जटिलता)]] है, क्योंकि यह लॉग स्पेस में लॉग-स्पेस ऑरेकल क्वेरीज़ (मोटे तौर पर कहें तो, फ़ंक्शन कॉल जो लॉग स्पेस का उपयोग करते हैं) का अनुकरण कर सकता है, प्रत्येक क्वेरी के लिए समान स्पेस का पुन: उपयोग कर सकता है।
एल अपने लिए [[कम (जटिलता)]] है, क्योंकि यह लॉग स्पेस में लॉग-स्पेस ऑरेकल क्वेरीज़ (मोटे तौर पर कहें तब , फलन कॉल जो लॉग स्पेस का उपयोग करते हैं) का अनुकरण कर सकता है, प्रत्येक क्वेरी के लिए समान स्पेस का पुन: उपयोग कर सकता है।


==अन्य उपयोग==
==अन्य उपयोग==
Line 39: Line 37:
लॉगस्पेस का मुख्य विचार यह है कि कोई व्यक्ति लॉगस्पेस में एक बहुपद-परिमाण संख्या को संग्रहीत कर सकता है और इसका उपयोग इनपुट की स्थिति के पॉइंटर्स को याद रखने के लिए कर सकता है।
लॉगस्पेस का मुख्य विचार यह है कि कोई व्यक्ति लॉगस्पेस में एक बहुपद-परिमाण संख्या को संग्रहीत कर सकता है और इसका उपयोग इनपुट की स्थिति के पॉइंटर्स को याद रखने के लिए कर सकता है।


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


==यह भी देखें==
==यह भी देखें==

Revision as of 17:34, 21 July 2023

कम्प्यूटेशनल जटिलता सिद्धांत में, एल (जिसे एलएसपीएसीई या डीएलओजीस्पेस के रूप में भी जाना जाता है) जटिलता वर्ग है जिसमें निर्णय समस्याएं सम्मिलित हैं जिन्हें लिखने योग्य मेमोरी स्पेस (कम्प्यूटेशनल संसाधन) की लॉगरिदमिक मात्रा का उपयोग करके नियतात्मक ट्यूरिंग मशीन द्वारा हल किया जा सकता है।[1][2] औपचारिक रूप से, ट्यूरिंग मशीन में दो टेप होते हैं, जिनमें से एक इनपुट को एनकोड करता है और इसे केवल पढ़ा जा सकता है,[3] जबकि दूसरे टेप का आकार लघुगणकीय है किन्तु इसे पढ़ा भी जा सकता है और लिखा भी जा सकता है। लॉगरिदमिक स्थान इनपुट में सूचक (कंप्यूटर प्रोग्रामिंग) की निरंतर संख्या रखने के लिए पर्याप्त है[1]और बूलियन फ़्लैग की एक लघुगणकीय संख्या और अनेक बुनियादी लॉगस्पेस एल्गोरिदम इस तरह से मेमोरी का उपयोग करते हैं।

संपूर्ण समस्याएँ और तार्किक लक्षण वर्णन

एल में प्रत्येक गैर-तुच्छ समस्या लॉग-स्पेस कटौती के तहत पूर्ण (जटिलता) है,[4] इसलिए एल-पूर्णता की सार्थक धारणाओं की पहचान करने के लिए कमजोर कटौती की आवश्यकता होती है, सबसे सामान्य है एफओ (जटिलता)|प्रथम-क्रम प्रथम-क्रम कमी।

ओमर रींगोल्ड द्वारा 2004 के एक परिणाम से पता चलता है कि यूएसटीसीओएन किसी दिए गए अप्रत्यक्ष ग्राफ़ में दो शीर्षों के मध्य एक पथ उपस्थित है या नहीं की समस्या एल में है जो दर्शाता है कि एल = एसएल (जटिलता), क्योंकि यूएसटीसीओएन एसएल-पूर्ण है।[5]

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

संबंधित जटिलता वर्ग

एल एनएल (जटिलता) का एक उपवर्ग है, जो एक गैर-नियतात्मक ट्यूरिंग मशीन पर लघुगणकीय स्थान में निर्णय लेने योग्य भाषाओं का वर्ग है। एनएल में एक समस्या को गैर-नियतात्मक मशीन के राज्यों और राज्य संक्रमणों का प्रतिनिधित्व करने वाले एक निर्देशित ग्राफ में पहुंच की समस्या में तब्दील किया जा सकता है, और लॉगरिदमिक स्पेस बाउंड का तात्पर्य है कि इस ग्राफ में कोने और किनारों की बहुपद संख्या है, जिससे यह एनएल का अनुसरण करता है नियतात्मक बहुपद समय में हल करने योग्य समस्याओं की जटिलता वर्ग पी (जटिलता) में निहित है।[6] इस प्रकार L ⊆ NL ⊆ ⊆ P. L को P में सम्मिलित करने को और अधिक सीधे तौर पर सिद्ध किया जा सकता है: O (log n) स्पेस का उपयोग करने वाला एक निर्णायक 2 से अधिक का उपयोग नहीं कर सकता हैओ(लॉग एन)=एनO(1) समय, क्योंकि यह संभावित कॉन्फ़िगरेशन की कुल संख्या है।

'एल' आगे वर्ग 'एनसी (जटिलता)' से निम्नलिखित तरीके से संबंधित है: 'एनसी'1 ⊆ L ⊆ NL ⊆ NC2. शब्दों में, बहुपद संख्या O(n) वाला एक समानांतर कंप्यूटर C दिया गया हैk) कुछ स्थिर k के लिए प्रोसेसर, कोई भी समस्या जिसे C पर O(लॉग एन) समय में हल किया जा सकता है, वह 'L' में है, और 'L' में कोई भी समस्या O(लॉग) समय में हल की जा सकती है2 n) C पर समय।

कंप्यूटर विज्ञान में अनसुलझी समस्याओं की महत्वपूर्ण सूची में यह सम्मिलित है कि क्या एल=पी,[2]और क्या एल = एनएल।[7] यह भी ज्ञात नहीं है कि एल = एनपी (जटिलता)।[8] फलन समस्याओं का संबंधित वर्ग FL (जटिलता) है। FL का उपयोग अधिकांशतः लॉगस्पेस कटौती को परिभाषित करने के लिए किया जाता है।

अतिरिक्त गुण

एल अपने लिए कम (जटिलता) है, क्योंकि यह लॉग स्पेस में लॉग-स्पेस ऑरेकल क्वेरीज़ (मोटे तौर पर कहें तब , फलन कॉल जो लॉग स्पेस का उपयोग करते हैं) का अनुकरण कर सकता है, प्रत्येक क्वेरी के लिए समान स्पेस का पुन: उपयोग कर सकता है।

अन्य उपयोग

लॉगस्पेस का मुख्य विचार यह है कि कोई व्यक्ति लॉगस्पेस में एक बहुपद-परिमाण संख्या को संग्रहीत कर सकता है और इसका उपयोग इनपुट की स्थिति के पॉइंटर्स को याद रखने के लिए कर सकता है।

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

यह भी देखें

  • एल/पॉली, एल का एक गैर-समान संस्करण जो बहुपद-आकार के शाखा कार्यक्रमों की जटिलता को दर्शाता है

टिप्पणियाँ

  1. ↑ 1.0 1.1 Sipser (1997), Definition 8.12, p. 295.
  2. ↑ 2.0 2.1 Garey & Johnson (1979), p. 177.
  3. ↑ On a read/write input tape, a linear amount of memory could be obtained by packing of symbols (as in the proof of the linear speedup theorem), thus evading the logspace contraint.
  4. ↑ See Garey & Johnson (1979), Theorem 7.13 (claim 2), p. 179.
  5. ↑ Reingold, Omer (2005). Undirected ST-connectivity in log-space. STOC'05: Proceedings of the 37th Annual ACM Symposium on Theory of Computing. ACM, New York. pp. 376–385. doi:10.1145/1060590.1060647. MR 2181639. ECCC TR04-094.
  6. ↑ Sipser (1997), Corollary 8.21, p. 299.
  7. ↑ Sipser (1997), p. 297; Garey & Johnson (1979), p. 180.
  8. ↑ "Complexity theory - is it possible that $L=NP$?".


संदर्भ

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=एल_(जटिलता)&oldid=227782’