एल (जटिलता)
कम्प्यूटेशनल जटिलता सिद्धांत में, एल (जिसे एलएसपीएसीई या डीएलओजीस्पेस के रूप में भी जाना जाता है) जटिलता वर्ग है जिसमें निर्णय समस्याएं शामिल हैं जिन्हें लिखने योग्य मेमोरी स्पेस (कम्प्यूटेशनल संसाधन) की लॉगरिदमिक मात्रा का उपयोग करके नियतात्मक ट्यूरिंग मशीन द्वारा हल किया जा सकता है।[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.0 1.1 Sipser (1997), Definition 8.12, p. 295.
- ↑ 2.0 2.1 Garey & Johnson (1979), p. 177.
- ↑ 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.
- ↑ See Garey & Johnson (1979), Theorem 7.13 (claim 2), p. 179.
- ↑ 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.
- ↑ Sipser (1997), Corollary 8.21, p. 299.
- ↑ Sipser (1997), p. 297; Garey & Johnson (1979), p. 180.
- ↑ "Complexity theory - is it possible that $L=NP$?".
संदर्भ
- Arora, Sanjeev; Barak, Boaz (2009). Computational complexity. A modern approach. Cambridge University Press. ISBN 978-0-521-42426-4. Zbl 1193.68112.
- Papadimitriou, Christos (1993). Computational Complexity (1st ed.). Addison Wesley. Chapter 16: Logarithmic space, pp. 395–408. ISBN 0-201-53082-1.
- Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. Section 8.4: The Classes L and NL, pp. 294–296. ISBN 0-534-94728-X.
- Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. Section 7.5: Logarithmic Space, pp. 177–181. ISBN 0-7167-1045-5.
- Cook, Stephen A.; McKenzie, Pierre (1987). "Problems Complete for Deterministic Logarithmic Space" (PDF). Journal of Algorithms. 8 (3): 385–394. doi:10.1016/0196-6774(87)90018-6. ISSN 0196-6774.
