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

From Vigyanwiki
(Created page with "{{short description|Complexity class (logarithmic space)}} {{redirect-distinguish|Logspace|Logscale}} कम्प्यूटेशनल जटिलता सिद्ध...")
 
No edit summary
 
(5 intermediate revisions by 3 users not shown)
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>''O''(log ''n'')</sup> = ''n<sup>O</sup>''<sup>(1)</sup> समय से अधिक का उपयोग नहीं कर सकता है , क्योंकि यह संभावित कॉन्फ़िगरेशन की कुल संख्या है।
'एनसी'<sup>1</sup> ⊆ L ⊆ NL ⊆ NC<sup>2</sup>.
शब्दों में, बहुपद संख्या 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} }}}}
'एल' आगे क्लास '[[एनसी (जटिलता)|एनसी (कॉम्प्लेक्सिटी)]]' से निम्नलिखित विधि से संबंधित है: '''NC'''<sup>1</sup> ⊆ '''L''' ⊆ '''NL''' ⊆ '''NC'''<sup>2</sup>. शब्दों में, बहुपद संख्या ''O''(''n<sup>k</sup>'') वाला एक समानांतर कंप्यूटर C दिया गया है) कुछ स्थिर k के लिए प्रोसेसर, कोई भी समस्या जिसे C पर ''O''(log ''n'') समय में हल किया जा सकता है, वह 'L' में है, और 'L' में कोई भी समस्या ''O''(log<sup>2</sup> ''n'') पर समय समय में हल की जा सकती है ।


कंप्यूटर विज्ञान में अनसुलझी समस्याओं की महत्वपूर्ण सूची में यह शामिल है कि क्या एल=पी,<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>
महत्वपूर्ण ओपन प्रॉब्लम है कि क्या एल = पी,<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 का उपयोग अक्सर लॉगस्पेस कटौती को परिभाषित करने के लिए किया जाता है।
 
फंक्शन प्रॉब्लम का संबंधित क्लास FL (कॉम्प्लेक्सिटी) है। FL का उपयोग अधिकांशतः लॉगस्पेस रिडक्शन को परिभाषित करने के लिए किया जाता है।


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


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


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


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


==टिप्पणियाँ==
==टिप्पणियाँ==
Line 56: Line 53:


{{ComplexityClasses}}
{{ComplexityClasses}}
[[Category: जटिलता वर्ग]]


[[Category: Machine Translated Page]]
[[Category:Collapse templates]]
[[Category:Created On 10/07/2023]]
[[Category:Created On 10/07/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists]]
[[Category:Pages with script errors]]
[[Category:Sidebars with styles needing conversion]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates generating microformats]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that are not mobile friendly]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:Wikipedia metatemplates]]
[[Category:जटिलता वर्ग]]

Latest revision as of 10:14, 28 July 2023

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

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

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

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

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

संबंधित कॉम्प्लेक्सिटी क्लास

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

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

महत्वपूर्ण ओपन प्रॉब्लम है कि क्या एल = पी,[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=228212’