एल (जटिलता)
कम्प्यूटेशनल कॉम्प्लेक्सिटी थ्योरी में, एल (जिसे एलएसपीएसीई या डीएलओजीस्पेस के रूप में भी जाना जाता है) कॉम्प्लेक्सिटी क्लास है जिसमें डिसिशन प्रॉब्लम सम्मिलित हैं जिन्हें लिखने योग्य मेमोरी स्पेस (कम्प्यूटेशनल संसाधन) की लॉगरिदमिक मात्रा का उपयोग करके डेटर्मिनिस्टिक ट्यूरिंग मशीन द्वारा हल किया जा सकता है।[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.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.
