स्पेस कम्प्लेक्सिटी: Difference between revisions
From Vigyanwiki
(Created page with "{{Short description|Computer memory needed by an algorithm}} एक कलन विधि या कंप्यूटर प्रोग्राम की स्प...") |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Computer memory needed by an algorithm}} | {{Short description|Computer memory needed by an algorithm}} | ||
एक [[कलन विधि]] या [[कंप्यूटर प्रोग्राम]] की स्पेस जटिलता इनपुट की विशेषताओं के एक फ़ंक्शन के रूप में [[कम्प्यूटेशनल समस्या]] के एक उदाहरण को हल करने के लिए आवश्यक मेमोरी स्पेस की मात्रा है। यह एक एल्गोरिदम द्वारा पूरी तरह से निष्पादित होने तक आवश्यक मेमोरी है।<ref>{{citation|title=Optimal Reliability Modeling: Principles and Applications|first1=Way|last1=Kuo|first2=Ming J.|last2=Zuo|publisher=John Wiley & Sons|year=2003|isbn=9780471275459|url=https://books.google.com/books?id=vdZ4Bm-LnHMC&pg=PA62|page=62}}</ref> इसमें इसके इनपुट द्वारा उपयोग की जाने वाली मेमोरी स्पेस, जिसे इनपुट स्पेस कहा जाता है, और निष्पादन के | एक [[कलन विधि]] या [[कंप्यूटर प्रोग्राम]] की स्पेस जटिलता इनपुट की विशेषताओं के एक फ़ंक्शन के रूप में [[कम्प्यूटेशनल समस्या]] के एक उदाहरण को हल करने के लिए आवश्यक मेमोरी स्पेस की मात्रा है। यह एक एल्गोरिदम द्वारा पूरी तरह से निष्पादित होने तक आवश्यक मेमोरी है।<ref>{{citation|title=Optimal Reliability Modeling: Principles and Applications|first1=Way|last1=Kuo|first2=Ming J.|last2=Zuo|publisher=John Wiley & Sons|year=2003|isbn=9780471275459|url=https://books.google.com/books?id=vdZ4Bm-LnHMC&pg=PA62|page=62}}</ref> इसमें इसके इनपुट द्वारा उपयोग की जाने वाली मेमोरी स्पेस, जिसे इनपुट स्पेस कहा जाता है, और निष्पादन के समय उपयोग की जाने वाली कोई अन्य (सहायक) मेमोरी सम्मिलित है जिसे सहायक स्पेस कहा जाता है। | ||
समय जटिलता के समान | समय जटिलता के समान स्पेस जटिलता को सम्मिलित [[बड़ा ओ अंकन]] में स्पर्शोन्मुख रूप से व्यक्त किया जाता है, जैसे कि <math>O(n),</math> | ||
<math>O(n\log n),</math> <math>O(n^\alpha),</math> <math>O(2^n),</math> आदि, | <math>O(n\log n),</math> <math>O(n^\alpha),</math> <math>O(2^n),</math> आदि, जहाँ {{mvar|n}} स्पेस जटिलता को प्रभावित करने वाले इनपुट की एक विशेषता है। | ||
== | ==स्पेस जटिलता वर्ग== | ||
[[समय]] जटिलता वर्गों [[DTIME]]|DTIME(f(n)) और NTIME|NTIME(f(n)) के अनुरूप, जटिलता वर्ग [[DSPACE]]|DSPACE(f(n)) और [[NSPACE]]|NSPACE(f(n)) सेट हैं ऐसी भाषाएँ जो नियतात्मक (क्रमशः, गैर-नियतात्मक) [[ट्यूरिंग मशीन]] | [[समय]] जटिलता वर्गों [[DTIME|'''DTIME''']]|DTIME(f(n)) और '''NTIME'''|NTIME(f(n)) के अनुरूप, जटिलता वर्ग [[DSPACE|'''DSPACE''']]|DSPACE(f(n)) और [[NSPACE|'''NSPACE''']]|NSPACE(f(n)) सेट हैं ऐसी भाषाएँ जो नियतात्मक (क्रमशः, गैर-नियतात्मक) [[ट्यूरिंग मशीन]] जो <math>O(f(n))</math> स्थान का उपयोग करती हैं। '''स्पेस''' जटिलता वर्ग [[PSPACE]] और [[NPSPACE]] अनुमति देते हैं <math>f</math> [[पी (जटिलता)]] और [[एनपी (जटिलता)]] के अनुरूप, कोई भी बहुपद होना। वह है, | ||
<math display=block>\mathsf{PSPACE} = \bigcup_{c \in \Z^+} \mathsf{DSPACE}(n^c)</math> | <math display=block>\mathsf{PSPACE} = \bigcup_{c \in \Z^+} \mathsf{DSPACE}(n^c)</math> | ||
और | और | ||
| Line 15: | Line 15: | ||
==वर्गों के बीच संबंध== | ==वर्गों के बीच संबंध== | ||
[[अंतरिक्ष पदानुक्रम प्रमेय]] बताता है कि, सभी [[अंतरिक्ष-निर्माण योग्य कार्य]] | [[अंतरिक्ष पदानुक्रम प्रमेय|स्पेस पदानुक्रम प्रमेय]] बताता है कि, सभी [[अंतरिक्ष-निर्माण योग्य कार्य|स्पेस -निर्माण योग्य कार्य]] के लिए<math>f(n),</math>एक समस्या उपस्थित है जिसे <math>f(n),</math> मेमोरी स्पेस वाली मशीन द्वारा हल किया जा सकता है किंतु <math>f(n),</math> से कम स्पेस वाली मशीन द्वारा हल नहीं किया जा सकता है . | ||
जटिलता वर्गों के बीच निम्नलिखित नियंत्रण कायम हैं।<ref>{{citation |title=Computational Complexity : A Modern Approach |edition=draft|year=2007|first1=Sanjeev|last1=Arora|author1-link=Sanjeev Arora|first2=Boaz|last2=Barak|isbn=9780511804090 |page=76 |url=https://theory.cs.princeton.edu/complexity/book.pdf}}</ref> | जटिलता वर्गों के बीच निम्नलिखित नियंत्रण कायम हैं।<ref>{{citation |title=Computational Complexity : A Modern Approach |edition=draft|year=2007|first1=Sanjeev|last1=Arora|author1-link=Sanjeev Arora|first2=Boaz|last2=Barak|isbn=9780511804090 |page=76 |url=https://theory.cs.princeton.edu/complexity/book.pdf}}</ref> | ||
<math display=block>\mathsf{DTIME}(f(n)) \subseteq \mathsf{DSPACE}(f(n)) \subseteq \mathsf{NSPACE}(f(n)) \subseteq \mathsf{DTIME}\left(2^{O(f(n))}\right)</math> | <math display=block>\mathsf{DTIME}(f(n)) \subseteq \mathsf{DSPACE}(f(n)) \subseteq \mathsf{NSPACE}(f(n)) \subseteq \mathsf{DTIME}\left(2^{O(f(n))}\right)</math> | ||
इसके | इसके अतिरिक्त सैविच का प्रमेय विपरीत रोकथाम देता है कि यदि <math>f \in \Omega(\log(n)),</math> | ||
<math display=block>\mathsf{NSPACE}(f(n)) \subseteq \mathsf{DSPACE}\left((f(n))^2\right).</math> | <math display=block>\mathsf{NSPACE}(f(n)) \subseteq \mathsf{DSPACE}\left((f(n))^2\right).</math> | ||
प्रत्यक्ष परिणाम के रूप में, <math>\mathsf{PSPACE} = \mathsf{NPSPACE}.</math> यह परिणाम आश्चर्यजनक है क्योंकि यह बताता है कि गैर-नियतिवाद किसी समस्या को हल करने के लिए आवश्यक स्थान को केवल थोड़ी मात्रा में कम कर सकता है। इसके विपरीत | प्रत्यक्ष परिणाम के रूप में, <math>\mathsf{PSPACE} = \mathsf{NPSPACE}.</math> यह परिणाम आश्चर्यजनक है क्योंकि यह बताता है कि गैर-नियतिवाद किसी समस्या को हल करने के लिए आवश्यक स्थान को केवल थोड़ी मात्रा में कम कर सकता है। इसके विपरीत घातीय समय परिकल्पना का अनुमान है कि समय जटिलता के लिए, नियतात्मक और गैर-नियतात्मक जटिलता के बीच एक घातीय अंतर हो सकता है। | ||
इमरमैन-स्ज़ेलेपेसेनी प्रमेय कहता है कि, फिर से <math>f\in\Omega(\log(n)),</math> <math>\mathsf{NSPACE}(f(n))</math> पूरकता के तहत बंद कर दिया गया है। यह समय और स्थान जटिलता वर्गों के बीच एक और गुणात्मक अंतर दिखाता है, क्योंकि गैर-नियतात्मक समय जटिलता वर्गों को पूरकता के तहत बंद नहीं माना जाता है; उदाहरण के लिए, यह अनुमान लगाया गया है कि | इमरमैन-स्ज़ेलेपेसेनी प्रमेय कहता है कि, फिर से <math>f\in\Omega(\log(n)),</math> <math>\mathsf{NSPACE}(f(n))</math> पूरकता के तहत बंद कर दिया गया है। यह समय और स्थान जटिलता वर्गों के बीच एक और गुणात्मक अंतर दिखाता है, क्योंकि गैर-नियतात्मक समय जटिलता वर्गों को पूरकता के तहत बंद नहीं माना जाता है; उदाहरण के लिए, यह अनुमान लगाया गया है कि NP ≠ co-NP.।<ref>{{citation | ||
| last = Immerman | first = Neil | authorlink = Neil Immerman | | last = Immerman | first = Neil | authorlink = Neil Immerman | ||
| doi = 10.1137/0217058 | | doi = 10.1137/0217058 | ||
| Line 40: | Line 40: | ||
| volume = 33 | | volume = 33 | ||
| year = 1987}}</ref> | | year = 1987}}</ref> | ||
==लॉगस्पेस== | |||
[[एल (जटिलता)|एल]] या लॉगस्पेस समस्याओं का समूह है जिसे इनपुट आकार के संबंध में केवल <math>O(\log n)</math> मेमोरी स्पेस का उपयोग करके एक नियतात्मक ट्यूरिंग मशीन द्वारा हल किया जा सकता है। यहां तक कि एक एकल काउंटर जो संपूर्ण <math>n</math>-बिट इनपुट को अनुक्रमित कर सकता है, उसे <math>\log n</math> स्पेस की आवश्यकता होती है, इसलिए लॉगस्पेस एल्गोरिदम केवल काउंटरों की एक स्थिर संख्या या समान बिट जटिलता के अन्य चर बनाए रख सकते हैं। | |||
लॉगस्पेस और अन्य सब-लीनियर स्पेस जटिलता बड़े डेटा को संसाधित करते समय उपयोगी होती है जो कंप्यूटर की [[रैंडम एक्सेस मेमोरी]] में फिट नहीं हो सकती है। वे [[स्ट्रीमिंग एल्गोरिदम]] से संबंधित हैं, किंतु केवल यह सीमित करते हैं कि कितनी मेमोरी का उपयोग किया जा सकता है, जबकि स्ट्रीमिंग एल्गोरिदम में एल्गोरिदम में इनपुट को कैसे फीड किया जाता है, इस पर और भी बाधाएं हैं। | |||
[[ | |||
यह वर्ग [[छद्म यादृच्छिकता]] और व्युत्पन्नता के क्षेत्र में भी उपयोग देखता है, जहां शोधकर्ता L = RL की खुली समस्या पर विचार करते हैं।<ref>{{citation | |||
यह वर्ग [[छद्म यादृच्छिकता]] और व्युत्पन्नता के क्षेत्र में भी उपयोग देखता है, जहां शोधकर्ता | |||
| last = Nisan | first = Noam | author-link = Noam Nisan | | last = Nisan | first = Noam | author-link = Noam Nisan | ||
| contribution = RL ⊆ SC | | contribution = RL ⊆ SC | ||
| Line 66: | Line 65: | ||
| title = STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing | | title = STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing | ||
| year = 2006| s2cid = 17360260 }}</ref> | | year = 2006| s2cid = 17360260 }}</ref> | ||
संबंधित गैर-नियतात्मक | |||
संबंधित गैर-नियतात्मक स्पेस जटिलता वर्ग [[एनएल (जटिलता)]] है। | |||
==सहायक स्थान जटिलता== | ==सहायक स्थान जटिलता== | ||
सहायक स्थान शब्द का तात्पर्य इनपुट द्वारा उपभोग किए गए स्थान के अलावा अन्य स्थान से है। सहायक स्पेस जटिलता को औपचारिक रूप से एक ट्यूरिंग मशीन के संदर्भ में परिभाषित किया जा सकता है जिसमें एक अलग इनपुट टेप होता है जिसे लिखा नहीं जा सकता, केवल पढ़ा जा सकता है, और एक पारंपरिक कार्यरत टेप जिसे लिखा जा सकता है। फिर सहायक स्थान जटिलता को कार्यशील टेप के माध्यम से परिभाषित (और विश्लेषण) किया जाता है। उदाहरण के लिए, <math>n</math> नोड्स के साथ एक संतुलित बाइनरी ट्री की गहराई-पहली खोज पर विचार करें: इसकी सहायक स्थान जटिलता <math>\Theta(\log n).</math> है। | |||
शब्द | |||
सहायक | |||
फिर सहायक स्थान जटिलता को कार्यशील टेप के माध्यम से परिभाषित (और विश्लेषण) किया जाता है। | |||
उदाहरण के लिए, बाइनरी ट्री की | |||
==यह भी देखें== | ==यह भी देखें== | ||
* {{annotated link| | * {{annotated link|एल्गोरिदम का विश्लेषण}} | ||
* {{annotated link| | * {{annotated link|कम्प्यूटेशनल जटिलता सिद्धांत}} | ||
* {{annotated link| | * {{annotated link|कम्प्यूटेशनल संसाधन}} | ||
==संदर्भ== | ==संदर्भ== | ||
Revision as of 09:20, 4 July 2023
एक कलन विधि या कंप्यूटर प्रोग्राम की स्पेस जटिलता इनपुट की विशेषताओं के एक फ़ंक्शन के रूप में कम्प्यूटेशनल समस्या के एक उदाहरण को हल करने के लिए आवश्यक मेमोरी स्पेस की मात्रा है। यह एक एल्गोरिदम द्वारा पूरी तरह से निष्पादित होने तक आवश्यक मेमोरी है।[1] इसमें इसके इनपुट द्वारा उपयोग की जाने वाली मेमोरी स्पेस, जिसे इनपुट स्पेस कहा जाता है, और निष्पादन के समय उपयोग की जाने वाली कोई अन्य (सहायक) मेमोरी सम्मिलित है जिसे सहायक स्पेस कहा जाता है।
समय जटिलता के समान स्पेस जटिलता को सम्मिलित बड़ा ओ अंकन में स्पर्शोन्मुख रूप से व्यक्त किया जाता है, जैसे कि आदि, जहाँ n स्पेस जटिलता को प्रभावित करने वाले इनपुट की एक विशेषता है।
स्पेस जटिलता वर्ग
समय जटिलता वर्गों DTIME|DTIME(f(n)) और NTIME|NTIME(f(n)) के अनुरूप, जटिलता वर्ग DSPACE|DSPACE(f(n)) और NSPACE|NSPACE(f(n)) सेट हैं ऐसी भाषाएँ जो नियतात्मक (क्रमशः, गैर-नियतात्मक) ट्यूरिंग मशीन जो स्थान का उपयोग करती हैं। स्पेस जटिलता वर्ग PSPACE और NPSPACE अनुमति देते हैं पी (जटिलता) और एनपी (जटिलता) के अनुरूप, कोई भी बहुपद होना। वह है,
और
वर्गों के बीच संबंध
स्पेस पदानुक्रम प्रमेय बताता है कि, सभी स्पेस -निर्माण योग्य कार्य के लिएएक समस्या उपस्थित है जिसे मेमोरी स्पेस वाली मशीन द्वारा हल किया जा सकता है किंतु से कम स्पेस वाली मशीन द्वारा हल नहीं किया जा सकता है .
जटिलता वर्गों के बीच निम्नलिखित नियंत्रण कायम हैं।[2]
इसके अतिरिक्त सैविच का प्रमेय विपरीत रोकथाम देता है कि यदि
प्रत्यक्ष परिणाम के रूप में, यह परिणाम आश्चर्यजनक है क्योंकि यह बताता है कि गैर-नियतिवाद किसी समस्या को हल करने के लिए आवश्यक स्थान को केवल थोड़ी मात्रा में कम कर सकता है। इसके विपरीत घातीय समय परिकल्पना का अनुमान है कि समय जटिलता के लिए, नियतात्मक और गैर-नियतात्मक जटिलता के बीच एक घातीय अंतर हो सकता है।
इमरमैन-स्ज़ेलेपेसेनी प्रमेय कहता है कि, फिर से पूरकता के तहत बंद कर दिया गया है। यह समय और स्थान जटिलता वर्गों के बीच एक और गुणात्मक अंतर दिखाता है, क्योंकि गैर-नियतात्मक समय जटिलता वर्गों को पूरकता के तहत बंद नहीं माना जाता है; उदाहरण के लिए, यह अनुमान लगाया गया है कि NP ≠ co-NP.।[3][4]
लॉगस्पेस
एल या लॉगस्पेस समस्याओं का समूह है जिसे इनपुट आकार के संबंध में केवल मेमोरी स्पेस का उपयोग करके एक नियतात्मक ट्यूरिंग मशीन द्वारा हल किया जा सकता है। यहां तक कि एक एकल काउंटर जो संपूर्ण -बिट इनपुट को अनुक्रमित कर सकता है, उसे स्पेस की आवश्यकता होती है, इसलिए लॉगस्पेस एल्गोरिदम केवल काउंटरों की एक स्थिर संख्या या समान बिट जटिलता के अन्य चर बनाए रख सकते हैं।
लॉगस्पेस और अन्य सब-लीनियर स्पेस जटिलता बड़े डेटा को संसाधित करते समय उपयोगी होती है जो कंप्यूटर की रैंडम एक्सेस मेमोरी में फिट नहीं हो सकती है। वे स्ट्रीमिंग एल्गोरिदम से संबंधित हैं, किंतु केवल यह सीमित करते हैं कि कितनी मेमोरी का उपयोग किया जा सकता है, जबकि स्ट्रीमिंग एल्गोरिदम में एल्गोरिदम में इनपुट को कैसे फीड किया जाता है, इस पर और भी बाधाएं हैं।
यह वर्ग छद्म यादृच्छिकता और व्युत्पन्नता के क्षेत्र में भी उपयोग देखता है, जहां शोधकर्ता L = RL की खुली समस्या पर विचार करते हैं।[5][6]
संबंधित गैर-नियतात्मक स्पेस जटिलता वर्ग एनएल (जटिलता) है।
सहायक स्थान जटिलता
सहायक स्थान शब्द का तात्पर्य इनपुट द्वारा उपभोग किए गए स्थान के अलावा अन्य स्थान से है। सहायक स्पेस जटिलता को औपचारिक रूप से एक ट्यूरिंग मशीन के संदर्भ में परिभाषित किया जा सकता है जिसमें एक अलग इनपुट टेप होता है जिसे लिखा नहीं जा सकता, केवल पढ़ा जा सकता है, और एक पारंपरिक कार्यरत टेप जिसे लिखा जा सकता है। फिर सहायक स्थान जटिलता को कार्यशील टेप के माध्यम से परिभाषित (और विश्लेषण) किया जाता है। उदाहरण के लिए, नोड्स के साथ एक संतुलित बाइनरी ट्री की गहराई-पहली खोज पर विचार करें: इसकी सहायक स्थान जटिलता है।
यह भी देखें
- एल्गोरिदम का विश्लेषण – Study of resources used by an algorithm
- कम्प्यूटेशनल जटिलता सिद्धांत – Inherent difficulty of computational problems
- कम्प्यूटेशनल संसाधन – Something a computer needs needed to solve a problem, such as processing steps or memory
संदर्भ
- ↑ Kuo, Way; Zuo, Ming J. (2003), Optimal Reliability Modeling: Principles and Applications, John Wiley & Sons, p. 62, ISBN 9780471275459
- ↑ Arora, Sanjeev; Barak, Boaz (2007), Computational Complexity : A Modern Approach (PDF) (draft ed.), p. 76, ISBN 9780511804090
- ↑ Immerman, Neil (1988), "Nondeterministic space is closed under complementation" (PDF), SIAM Journal on Computing, 17 (5): 935–938, doi:10.1137/0217058, MR 0961049
- ↑ Szelepcsényi, Róbert (1987), "The method of forcing for nondeterministic automata", Bulletin of the EATCS, 33: 96–100
- ↑ Nisan, Noam (1992), "RL ⊆ SC", Proceedings of the 24th ACM Symposium on Theory of computing (STOC '92), Victoria, British Columbia, Canada, pp. 619–623, doi:10.1145/129712.129772, S2CID 11651375
{{citation}}: CS1 maint: location missing publisher (link). - ↑ Reingold, Omer; Trevisan, Luca; Vadhan, Salil (2006), "Pseudorandom walks on regular digraphs and the RL vs. L problem" (PDF), STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, New York: ACM, pp. 457–466, doi:10.1145/1132516.1132583, MR 2277171, S2CID 17360260
