View source for स्पेस कम्प्लेक्सिटी

{{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> इसमें इसके इनपुट द्वारा उपयोग की जाने वाली मेमोरी स्पेस, जिसे इनपुट स्पेस कहा जाता है, और निष्पादन के समय  उपयोग की जाने वाली कोई अन्य (सहायक) मेमोरी सम्मिलित  है जिसे सहायक स्पेस कहा जाता है।

समय कम्प्लेक्सिटी के समान स्पेस  कम्प्लेक्सिटी को सम्मिलित [[बड़ा ओ अंकन]] में स्पर्शोन्मुख रूप से व्यक्त किया जाता है, जैसे कि <math>O(n),</math>
<math>O(n\log n),</math> <math>O(n^\alpha),</math> <math>O(2^n),</math> आदि, जहाँ {{mvar|n}} स्पेस  कम्प्लेक्सिटी को प्रभावित करने वाले इनपुट की एक विशेषता है।

==स्पेस कम्प्लेक्सिटी वर्ग==

[[समय]] कम्प्लेक्सिटी वर्गों DTIME(f(n)) और NTIME(f(n)) के अनुरूप, कम्प्लेक्सिटी वर्ग DSPACE(f(n)) और 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{NPSPACE} = \bigcup_{c \in \Z^+} \mathsf{NSPACE}(n^c)</math>


==वर्गों के बीच संबंध==

[[अंतरिक्ष पदानुक्रम प्रमेय|स्पेस  पदानुक्रम प्रमेय]] बताता है कि, सभी  [[अंतरिक्ष-निर्माण योग्य कार्य|स्पेस -निर्माण योग्य कार्य]] के लिए<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>
<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>\mathsf{PSPACE} = \mathsf{NPSPACE}.</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
 | doi = 10.1137/0217058
 | issue = 5
 | journal = SIAM Journal on Computing
 | mr = 961049
 | pages = 935–938
 | title = Nondeterministic space is closed under complementation
 | url = http://www.cs.umass.edu/~immerman/pub/space.pdf
 | volume = 17
 | year = 1988}}</ref><ref>{{citation
 | last = Szelepcsényi | first = Róbert | author-link = Róbert Szelepcsényi
 | journal = Bulletin of the EATCS
 | pages = 96–100
 | title = The method of forcing for nondeterministic automata
 | volume = 33
 | 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
 | contribution = RL ⊆ SC
 | doi = 10.1145/129712.129772
 | location = Victoria, British Columbia, Canada
 | pages = 619–623
 | title = Proceedings of the 24th ACM Symposium on Theory of computing (STOC '92)
 | year = 1992| s2cid = 11651375 }}.</ref><ref>{{citation
 | last1 = Reingold | first1 = Omer | author1-link = Omer Reingold
 | last2 = Trevisan | first2 = Luca | author2-link = Luca Trevisan
 | last3 = Vadhan | first3 = Salil | author3-link = Salil Vadhan
 | contribution = Pseudorandom walks on regular digraphs and the RL vs. L problem
 | contribution-url = http://people.seas.harvard.edu/~salil/research/regular.pdf
 | doi = 10.1145/1132516.1132583
 | mr = 2277171
 | pages = 457–466
 | publisher = ACM | location = New York
 | title = STOC'06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing
 | year = 2006| s2cid = 17360260 }}</ref>

संबंधित गैर-नियतात्मक स्पेस  कम्प्लेक्सिटी वर्ग [[एनएल (जटिलता)|एनएल (कम्प्लेक्सिटी)]] है।

==सहायक स्थान कम्प्लेक्सिटी==
सहायक स्थान शब्द का तात्पर्य इनपुट द्वारा उपभोग किए गए स्थान के अलावा अन्य स्थान से है। सहायक स्पेस कम्प्लेक्सिटी को औपचारिक रूप से एक ट्यूरिंग मशीन के संदर्भ में परिभाषित किया जा सकता है जिसमें एक अलग इनपुट टेप होता है जिसे लिखा नहीं जा सकता, केवल पढ़ा जा सकता है, और एक पारंपरिक कार्यरत टेप जिसे लिखा जा सकता है। फिर सहायक स्थान कम्प्लेक्सिटी को कार्यशील टेप के माध्यम से परिभाषित (और विश्लेषण) किया जाता है। उदाहरण के लिए, <math>n</math> नोड्स के साथ एक संतुलित बाइनरी ट्री की गहराई-पहली खोज पर विचार करें: इसकी सहायक स्थान कम्प्लेक्सिटी <math>\Theta(\log n).</math> है।
==यह भी देखें                                                                                                                                                            ==

* {{annotated link|एल्गोरिदम का विश्लेषण}}
* {{annotated link|कम्प्यूटेशनल जटिलता सिद्धांत}}
* {{annotated link|कम्प्यूटेशनल संसाधन}}

==संदर्भ==

{{reflist}}

[[Category:Created On 27/06/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:कम्प्यूटेशनल जटिलता सिद्धांत]]
[[Category:कम्प्यूटेशनल संसाधन]]