एल (जटिलता): Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{short description|Complexity class (logarithmic space)}} | {{short description|Complexity class (logarithmic space)}} | ||
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, एल (जिसे एलएसपीएसीई या डीएलओजीस्पेस के रूप में भी जाना जाता है) [[जटिलता वर्ग]] है जिसमें [[निर्णय समस्या]] | [[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल कॉम्प्लेक्सिटी थ्योरी]] में, एल (जिसे एलएसपीएसीई या डीएलओजीस्पेस के रूप में भी जाना जाता है) [[जटिलता वर्ग|कॉम्प्लेक्सिटी क्लास]] है जिसमें [[निर्णय समस्या|डिसिशन]] प्रॉब्लम सम्मिलित हैं जिन्हें लिखने योग्य [[मेमोरी स्पेस (कम्प्यूटेशनल संसाधन)]] की लॉगरिदमिक मात्रा का उपयोग करके [[नियतात्मक ट्यूरिंग मशीन|डेटर्मिनिस्टिक ट्यूरिंग मशीन]] द्वारा हल किया जा सकता है।<ref name="sip295">{{harvtxt|Sipser|1997}}, Definition 8.12, p. 295.</ref><ref name="gj-177">{{harvtxt|Garey|Johnson|1979}}, p. 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. 179.</ref> इसलिए एल-पूर्णता की सार्थक धारणाओं की पहचान करने के लिए अशक्त रिडक्शन की आवश्यकता होती है, सबसे सामान्य है [[एफओ (जटिलता)|एफओ (कॉम्प्लेक्सिटी)]] फर्स्ट-आर्डर रिडक्शन है | ||
[[ओमर रींगोल्ड]] द्वारा 2004 के एक परिणाम से पता चलता है कि [[यूएसटीसीओएन]] किसी दिए गए [[अप्रत्यक्ष ग्राफ]] | [[ओमर रींगोल्ड]] द्वारा 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 17: | ||
| year = 2005}}</ref> | | year = 2005}}</ref> | ||
इसका एक परिणाम एल का एक सरल तार्किक लक्षण वर्णन है: इसमें एक अतिरिक्त कम्यूटिव [[ सकर्मक समापन | | इसका एक परिणाम एल का एक सरल तार्किक लक्षण वर्णन है: इसमें एक अतिरिक्त कम्यूटिव [[ सकर्मक समापन |ट्रांसिटिव क्लोसर]] ऑपरेटर के साथ फर्स्ट-आर्डर [[प्रथम-क्रम तर्क|लॉजिक]] में व्यक्त की जाने वाली स्पष्ट भाषाएं सम्मिलित हैं ([[ग्राफ सिद्धांत|ग्राफ थ्योरी]] के संदर्भ में यह प्रत्येक जुड़े घटक (ग्राफ थ्योरी ) को एक क्लिक (ग्राफ) में बदल देता है लिखित))। यह परिणाम डेटाबेस क्वेरी लैंग्वेज पर प्रयुक्त होता है: किसी क्वेरी की ''डेटा'' कॉम्प्लेक्सिटी को डेटा आकार को परिवर्तनीय इनपुट के रूप में मानते हुए एक निश्चित क्वेरी का उत्तर देने की कॉम्प्लेक्सिटी के रूप में परिभाषित किया गया है। इस उपाय के लिए [[संबंधपरक बीजगणित|रेलैसनल अलजेब्रा]] में उदाहरण के लिए व्यक्त की गई संपूर्ण जानकारी ([[शून्य (एसक्यूएल)|नल (एसक्यूएल)]] की कोई धारणा नहीं) के साथ संबंधपरक डेटाबेस के विरुद्ध प्रश्न एल में हैं। | ||
==संबंधित | ==संबंधित कॉम्प्लेक्सिटी क्लास == | ||
एल [[एनएल (जटिलता)]] का एक उपवर्ग है, जो एक [[गैर-नियतात्मक ट्यूरिंग मशीन]] पर | एल [[एनएल (जटिलता)|एनएल (कॉम्प्लेक्सिटी)]] का एक उपवर्ग है, जो एक [[गैर-नियतात्मक ट्यूरिंग मशीन|गैर-डेटर्मिनिस्टिक ट्यूरिंग मशीन]] पर लोगरिथ्मिक स्थान में डिसिशन लेने योग्य लैंग्वेज का क्लास है। एनएल में एक समस्या को नॉन-डेटर्मिनिस्टिक मशीन के स्टेट और स्टेट ट्रांजिसन का प्रतिनिधित्व करने वाले एक [[निर्देशित ग्राफ|दिरेक्टेद ग्राफ]] में पहुंच की समस्या में परिवर्तित किया जा सकता है, और लॉगरिदमिक स्पेस बाउंड का तात्पर्य है कि इस ग्राफ में कोने और किनारों की बहुपद संख्या है, जिससे यह एनएल का अनुसरण करता है डेटर्मिनिस्टिक बहुपद समय में हल करने योग्य समस्याओं की कॉम्प्लेक्सिटी क्लास [[पी (जटिलता)|पी (कॉम्प्लेक्सिटी)]] में निहित है।<ref>{{harvtxt|Sipser|1997}}, Corollary 8.21, p. 299.</ref> इस प्रकार L ⊆ NL ⊆ ⊆ P. L को P में सम्मिलित करने को और अधिक सीधे रूप से सिद्ध किया जा सकता है: ''O'' (log ''n'') स्पेस का उपयोग करने वाला एक निर्णायक 2<sup>''O''(log ''n'')</sup> = ''n<sup>O</sup>''<sup>(1)</sup> समय से अधिक का उपयोग नहीं कर सकता है , क्योंकि यह संभावित कॉन्फ़िगरेशन की कुल संख्या है। | ||
'एल' आगे | 'एल' आगे क्लास '[[एनसी (जटिलता)|एनसी (कॉम्प्लेक्सिटी)]]' से निम्नलिखित विधि से संबंधित है: '''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'') पर समय समय में हल की जा सकती है । | ||
' | |||
शब्दों में, बहुपद संख्या O(n) वाला एक समानांतर कंप्यूटर C दिया गया है | |||
महत्वपूर्ण ओपन प्रॉब्लम है कि क्या एल = पी,<ref name="gj-177"/> और क्या एल = एनएल<ref>{{harvtxt|Sipser|1997}}, p. 297; {{harvtxt|Garey|Johnson|1979}}, p. 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 37: | Line 36: | ||
लॉगस्पेस का मुख्य विचार यह है कि कोई व्यक्ति लॉगस्पेस में एक बहुपद-परिमाण संख्या को संग्रहीत कर सकता है और इसका उपयोग इनपुट की स्थिति के पॉइंटर्स को याद रखने के लिए कर सकता है। | लॉगस्पेस का मुख्य विचार यह है कि कोई व्यक्ति लॉगस्पेस में एक बहुपद-परिमाण संख्या को संग्रहीत कर सकता है और इसका उपयोग इनपुट की स्थिति के पॉइंटर्स को याद रखने के लिए कर सकता है। | ||
लॉगस्पेस क्लास इसलिए मॉडल गणना के लिए उपयोगी है जहां कंप्यूटर की [[ रैंडम एक्सेस मेमोरी |रैंडम एक्सेस मेमोरी]] में फिट होने के लिए इनपुट बहुत बड़ा है। लंबे [[डीएनए]] अनुक्रम और डेटाबेस समस्याओं के अच्छे उदाहरण हैं जहां किसी निश्चित समय में इनपुट का केवल एक स्थिर | लॉगस्पेस क्लास इसलिए मॉडल गणना के लिए उपयोगी है जहां कंप्यूटर की [[ रैंडम एक्सेस मेमोरी |रैंडम एक्सेस मेमोरी]] में फिट होने के लिए इनपुट बहुत बड़ा है। लंबे [[डीएनए]] अनुक्रम और डेटाबेस समस्याओं के अच्छे उदाहरण हैं जहां किसी निश्चित समय में इनपुट का केवल एक स्थिर भाग रैम में होगा और जहां हमारे पास निरीक्षण करने के लिए इनपुट के अगले भाग की गणना करने के लिए संकेतक हैं, इस प्रकार केवल लॉगरिदमिक मेमोरी का उपयोग किया जाता है। | ||
==यह भी देखें== | ==यह भी देखें== | ||
*एल/पॉली, एल का एक गैर-समान संस्करण जो बहुपद-आकार के | *एल/पॉली, एल का एक गैर-समान संस्करण जो बहुपद-आकार के ब्रांचिंग प्रोग्राम की कॉम्प्लेक्सिटी को दर्शाता है | ||
==टिप्पणियाँ== | ==टिप्पणियाँ== | ||
Revision as of 20:57, 21 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.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.
