स्पेस कम्प्लेक्सिटी

एक कलन विधि या कंप्यूटर प्रोग्राम की समष्टि सम्मिश्रता इनपुट की विशेषताओं के एक फ़ंक्शन के रूप में कम्प्यूटेशनल समस्या के एक उदाहरण को हल करने के लिए आवश्यक मेमोरी समष्टि की मात्रा है। यह एक एल्गोरिदम द्वारा पूरी तरह से निष्पादित होने तक आवश्यक मेमोरी है। इसमें इसके इनपुट द्वारा उपयोग की जाने वाली मेमोरी समष्टि, जिसे इनपुट समष्टि कहा जाता है, और निष्पादन के समय उपयोग की जाने वाली कोई अन्य (सहायक) मेमोरी सम्मिलित है जिसे सहायक समष्टि कहा जाता है।

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

समष्टि सम्मिश्रता वर्ग

समय सम्मिश्रता वर्गों DTIME(f(n)) और NTIME(f(n)) के अनुरूप, सम्मिश्रता वर्ग DSPACE(f(n)) और NSPACE(f(n)) सेट हैं ऐसी भाषाएँ जो नियतात्मक (क्रमशः, गैर-नियतात्मक) ट्यूरिंग मशीन जो $O(f(n))$ स्थान का उपयोग करती हैं। सम्मिश्रता वर्ग PSPACE और NPSPACE अनुमति देते हैं $f$ पी (सम्मिश्रता) और एनपी (सम्मिश्रता) के अनुरूप, कोई भी बहुपद होना। वह है,

$${\mathsf {PSPACE}}=\bigcup _{c\in \mathbb {Z} ^{+}}{\mathsf {DSPACE}}(n^{c})$$

और

$${\mathsf {NPSPACE}}=\bigcup _{c\in \mathbb {Z} ^{+}}{\mathsf {NSPACE}}(n^{c})$$

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

समष्टि पदानुक्रम प्रमेय बताता है कि, सभी समष्टि -निर्माण योग्य कार्य के लिए$f(n),$एक समस्या उपस्थित है जिसे $f(n),$ मेमोरी समष्टि वाली मशीन द्वारा हल किया जा सकता है किंतु $f(n),$ से कम समष्टि वाली मशीन द्वारा हल नहीं किया जा सकता है .

सम्मिश्रता वर्गों के बीच निम्नलिखित नियंत्रण कायम हैं।

$${\mathsf {DTIME}}(f(n))\subseteq {\mathsf {DSPACE}}(f(n))\subseteq {\mathsf {NSPACE}}(f(n))\subseteq {\mathsf {DTIME}}\left(2^{O(f(n))}\right)$$

इसके अतिरिक्त सैविच का प्रमेय विपरीत रोकथाम देता है कि यदि $f\in \Omega (\log(n)),$

$${\mathsf {NSPACE}}(f(n))\subseteq {\mathsf {DSPACE}}\left((f(n))^{2}\right).$$

प्रत्यक्ष परिणाम के रूप में, ${\mathsf {PSPACE}}={\mathsf {NPSPACE}}.$ यह परिणाम आश्चर्यजनक है क्योंकि यह बताता है कि गैर-नियतिवाद किसी समस्या को हल करने के लिए आवश्यक स्थान को केवल थोड़ी मात्रा में कम कर सकता है। इसके विपरीत घातीय समय परिकल्पना का अनुमान है कि समय सम्मिश्रता के लिए, नियतात्मक और गैर-नियतात्मक सम्मिश्रता के बीच एक घातीय अंतर हो सकता है।

इमरमैन-स्ज़ेलेपेसेनी प्रमेय कहता है कि, फिर से $f\in \Omega (\log(n)),$ ${\mathsf {NSPACE}}(f(n))$ पूरकता के तहत बंद कर दिया गया है। यह समय और स्थान सम्मिश्रता वर्गों के बीच एक और गुणात्मक अंतर दिखाता है, क्योंकि गैर-नियतात्मक समय सम्मिश्रता वर्गों को पूरकता के तहत बंद नहीं माना जाता है; उदाहरण के लिए, यह अनुमान लगाया गया है कि NP ≠ co-NP.।

लॉगसमष्टि

एल या लॉगसमष्टि समस्याओं का समूह है जिसे इनपुट आकार के संबंध में केवल $O(\log n)$ मेमोरी समष्टि का उपयोग करके एक नियतात्मक ट्यूरिंग मशीन द्वारा हल किया जा सकता है। यहां तक कि एक एकल काउंटर जो संपूर्ण $n$-बिट इनपुट को अनुक्रमित कर सकता है, उसे $\log n$ समष्टि की आवश्यकता होती है, इसलिए लॉगसमष्टि एल्गोरिदम केवल काउंटरों की एक स्थिर संख्या या समान बिट सम्मिश्रता के अन्य चर बनाए रख सकते हैं।

लॉगसमष्टि और अन्य सब-लीनियर समष्टि सम्मिश्रता बड़े डेटा को संसाधित करते समय उपयोगी होती है जो कंप्यूटर की रैंडम एक्सेस मेमोरी में फिट नहीं हो सकती है। वे स्ट्रीमिंग एल्गोरिदम से संबंधित हैं, किंतु केवल यह सीमित करते हैं कि कितनी मेमोरी का उपयोग किया जा सकता है, जबकि स्ट्रीमिंग एल्गोरिदम में एल्गोरिदम में इनपुट को कैसे फीड किया जाता है, इस पर और भी बाधाएं हैं।

यह वर्ग छद्म यादृच्छिकता और व्युत्पन्नता के क्षेत्र में भी उपयोग देखता है, जहां शोधकर्ता L = RL की खुली समस्या पर विचार करते हैं।

संबंधित गैर-नियतात्मक समष्टि सम्मिश्रता वर्ग एनएल (सम्मिश्रता) है।

सहायक स्थान सम्मिश्रता

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

यह भी देखें

• एल्गोरिदम का विश्लेषण – 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