समष्टि पदानुक्रम प्रमेय: Difference between revisions

Latest revision as of 22:36, 2 February 2024

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

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

स्पेस हायरार्की थ्योरम स्पेस-कंस्ट्रक्टिबल फंक्शन्स की अवधारणा पर निर्भर करते हैं। डेटर्मीनिस्टिक एवं नॉन-डेटर्मीनिस्टिक स्पेस हायरार्की थ्योरम बताते हैं कि सभी स्पेस-कंस्ट्रक्टिबल फंक्शन्स के लिए f(n), इस प्रकार है:

{\mathsf {SPACE}}\left(o(f(n))\right)\subsetneq {\mathsf {SPACE}}(f(n))

,

जहां स्पेस का तात्पर्य डीस्पेस या एनस्पेस है, और $o$ छोटे o नोटेशन को रेफेर करता है।

स्टेटमेंट

औपचारिक रूप से, फंक्शन $f:\mathbb {N} \longrightarrow \mathbb {N}$ स्पेस-कंस्ट्रक्टीबल है यदि $f(n)\geq \log ~n$ एवं वहाँ ट्यूरिंग मशीन उपस्थित है जो फंक्शन $f(n)$ की कंप्यूट स्पेस $O(f(n))$ में इनपुट $1^{n}$ के साथ प्रारंभ करते टाइम करता है, जहाँ $1^{n}$ n क्रमागत 1s की स्ट्रिंग का प्रतिनिधित्व करता है। अधिकांश सामान्य फंक्शन जिनके साथ हम कार्य करते हैं, वे स्पेस-कंस्ट्रक्टीबल हैं, जिनमें बहुपद, घातांक एवं लघुगणक सम्मिलित हैं।

प्रत्येक स्पेस-कंस्ट्रक्टीबल फंक्शन $f:\mathbb {N} \longrightarrow \mathbb {N}$ के लिए, वहाँ लैंग्वेज $L$ उपस्थित है जो स्पेस $O(f(n))$ में निर्णय लेने योग्य है किन्तु स्पेस $o(f(n))$ में नहीं है।

प्रूफ

गोल ऐसी लैंग्वेज को परिभाषित करना है जिसे स्पेस $o(f(n))$ में नहीं अपितु $O(f(n))$ में निश्चित किया जा सकता है। लैंग्वेज को L के रूप में परिभाषित किया गया है, $L=\{~(\langle M\rangle ,10^{k}):M{\mbox{ uses space }}\leq f(|\langle M\rangle ,10^{k}|){\mbox{ and time }}\leq 2^{f(|\langle M\rangle ,10^{k}|)}{\mbox{ and }}M{\mbox{ does not accept }}(\langle M\rangle ,10^{k})~\}$

किसी भी मशीन $M$ के लिए जो स्पेस $o(f(n))$ में लैंग्वेज सुनिश्चित करता है, $L$ $M$ की लैंग्वेज से कम से कम स्पेस पर भिन्न होगा, अर्थात्, कुछ बड़े पर्याप्त $k$ के लिए, $M$ स्पेस का उपयोग करेगा $\leq f(|\langle M\rangle ,10^{k}|)$ on $(\langle M\rangle ,10^{k})$ और इसलिए इसके मूल्य में भिन्नता होगी।

दूसरी ओर, $L$ , ${\mathsf {SPACE}}(f(n))$ में है। लैंग्वेज $L$ सुनिश्चित करने के लिए एल्गोरिदम इस प्रकार है:

इनपुट $x$ पर, $f(|x|)$ स्पेस-निर्माणशीलता का उपयोग और मार्क ऑफ करके कंप्यूट की जाती है, एवं $f(|x|)$ टेप की सेल को चिह्नित किया जाता है, जब भी इससे अधिक प्रयोग करने का प्रयास किया जाता है तो $f(|x|)$ सेल इसे अस्वीकार कर देती है।
यदि $x$ , $\langle M\rangle ,10^{k}$ का स्वरूप नहीं है, तो कुछ TM के लिए $M$ , अस्वीकार किया जाता है।
अधिक से अधिक इनपुट $x$ पर $M$ का अनुकरण करता है, $2^{f(|x|)}$ चरण ( $f(|x|)$ स्पेस का उपयोग करके) है। यदि सिमुलेशन $f(|x|)$ स्पेस से अधिक या उससे अधिक $2^{f(|x|)}$ ऑपरेशन का उपयोग करने का प्रयास करता है तो इसे अस्वीकार कर दिया जाता है।
यदि इस अनुकरण के टाइम $M$ ने $x$ को स्वीकार कर लिया है, तो इसे अस्वीकार अन्यथा स्वीकार कर लिया जाता है।

चरण 3 पर ध्यान दें: निष्पादन यहीं तक सीमित है, उस स्थिति से बचने के लिए $2^{f(|x|)}$ चरण जहां $M$ इनपुट $x$ पर नहीं रुकता है। अर्थात्, वह स्थिति जहाँ $M$ केवल स्थान का उपभोग करता है। $O(f(x))$ आवश्यकतानुसार, किन्तु अनंत टाइम तक उपयोग होता है।

उपरोक्त प्रूफ पीस्पेस की स्थिति में मान्य है, किन्तु एनपीस्पेस की स्थिति में कुछ परिवर्तन करने की आवश्यकता है। महत्वपूर्ण बिंदु यह है कि नियतात्मक TM पर, स्वीकृति एवं अस्वीकृति को विपरीत किया जा सकता है (चरण 4 के लिए महत्वपूर्ण), अन्य-नियतात्मक मशीन पर यह संभव नहीं है।

एनपीस्पेस की स्थिति में, $L$ को पुनः परिभाषित करने की आवश्यकता है:

$L=\{~(\langle M\rangle ,10^{k}):M{\mbox{ uses space }}\leq f(|\langle M\rangle ,10^{k}|){\mbox{ and }}M{\mbox{ accepts }}(\langle M\rangle ,10^{k})~\}$

अब, चरण 4 को संशोधित करके $L$ को स्वीकार करने के लिए एल्गोरिदम को परिवर्तित करने की आवश्यकता है:

यदि इस अनुकरण के टाइम $M$ ने $x$ को स्वीकार कर लिया है, तो स्वीकार करें; अन्यथा, अस्वीकार करें।

$L$ का उपयोग TM द्वारा $o(f(n))$ का उपयोग नहीं किया जा सकता है। यह मानते हुए कि $L$ का निर्णय कुछ TM $M$ उपयोग करके किया जा सकता है $o(f(n))$ सेल एवं इमरमैन-स्ज़ेलेपीसीसेनी थ्योरम का अनुसरण करते हुए, ${\overline {L}}$ को TM (जिसे ${\overline {M}}$ कहा जाता है) द्वारा $o(f(n))$ सेल का उपयोग करके भी निर्धारित किया जा सकता है। यहाँ विरोधाभास है, इसलिए धारणा असत्य होनी चाहिए:

यदि $w=(\langle {\overline {M}}\rangle ,10^{k})$ (कुछ बड़े पर्याप्त $k$ के लिए) ${\overline {L}}$ में नहीं है इसलिए $M$ इसे स्वीकार करेगा, इसलिए ${\overline {M}}$ $w$ को अस्वीकार करता है, इसलिए $w$ ${\overline {L}}$ में है (विरोधाभास)।
यदि $w=(\langle {\overline {M}}\rangle ,10^{k})$ (कुछ बड़े पर्याप्त $k$ के लिए) ${\overline {L}}$ में है इसलिए $M$ इसे अस्वीकार कर देगा ${\overline {M}}$ $w$ को स्वीकार करता है, इसलिए $w$ , ${\overline {L}}$ में नहीं है (विरोधाभास)।

कम्पेरिज़न और इम्प्रोवेमेन्ट्स

स्पेस हायरार्की थ्योरम कई विषयों में अनुरूप टाइम हायरार्की थेओरेम्स से अधिक सशक्त है:

इसके लिए केवल s(n) को कम से कम n के अतिरिक्त कम से कम log n होना आवश्यक है।
यह किसी भी स्पर्शोन्मुख अंतर के साथ वर्गों को भिन्न कर सकता है, जबकि टाइम हायरार्की थ्योरम के लिए उन्हें लोगरिथम फैक्टर द्वारा भिन्न करने की आवश्यकता होती है।
इसके लिए फंक्शन को टाइम-कंस्ट्रक्टीबल नहीं अपितु स्पेस-कंस्ट्रक्टीबल होना आवश्यक है।

टाइम की अपेक्षा में स्पेस में वर्गों को भिन्न करना सरल लगता है। वास्तव में, जबकि टाइम हायरार्की थ्योरम ने अपनी स्थापना के पश्चात से उल्लेखनीय सुधार देखा है, नॉन डिटरमिनिस्टिक स्पेस हायरार्की थ्योरम में कम से कम महत्वपूर्ण सुधार देखा गया है जिसे विलियम गेफ़र्ट ने अपने 2003 के पेपर स्पेस हायरार्की थ्योरम में संशोधित किया है। इस पेपर ने थ्योरम के कई सामान्यीकरण किये है:

यह स्पेस-निर्माण योग्यता की आवश्यकता को शिथिल करता है। केवल संघ वर्गों ${\mathsf {DSPACE}}(O(s(n))$ एवं ${\mathsf {DSPACE}}(o(s(n))$ को भिन्न करने के अतिरिक्त यह ${\mathsf {DSPACE}}(f(n))$ से ${\mathsf {DSPACE}}(g(n))$ को भिन्न करता है, जहाँ $f(n)$ आर्बिटरी है $O(s(n))$ फंक्शन एवं g(n) कंप्यूट योग्य $o(s(n))$ फंक्शन है। इन फंक्शन को स्पेस-कंस्ट्रक्टीबल या मोनोटोन बढ़ाने की आवश्यकता नहीं है।
यह यूनरी लैंग्वेज या टैली लैंग्वेज की पहचान करता है, जो वर्ग में है किन्तु दूसरे में नहीं है। मूल थ्योरम में, भिन्न करने वाली लैंग्वेज आर्बिटरी थी।
इसकी आवश्यकता नहीं है, $s(n)$ कम से कम log n होना चाहिए; यह कोई भी अन्य-नियतात्मक रूप से पूर्णतः स्पेस-कंस्ट्रक्टीबल कार्य हो सकता है।

रिफाइनमेंट स्पेस हायरार्की

यदि स्पेस को वर्णमाला के आकार पर विचार किए बिना उपयोग की गई सेल की नंबर के रूप में मापा जाता है, तो ${\mathsf {SPACE}}(f(n))={\mathsf {SPACE}}(O(f(n)))$ होता है, क्योंकि कोई भी बड़े वर्णमाला पर स्विच करके किसी भी रैखिक कम्प्रेशन को प्राप्त कर सकता है। चूँकि, बिट्स में स्पेस को मापने से, नियतात्मक स्पेस के लिए अधिक तीव्र पृथक्करण प्राप्त किया जा सकता है। गुणात्मक स्थिरांक तक परिभाषित होने के अतिरिक्त, स्पेस को अब योगात्मक स्थिरांक तक परिभाषित किया गया है। चूँकि, क्योंकि एक्सटर्नल स्पेस की किसी भी स्थिर मात्रा को कंटेंट्स को आंतरिक स्थिति में संग्रहीत करके बचाया जा सकता है, हमारे पास अभी भी ${\mathsf {SPACE}}(f(n))={\mathsf {SPACE}}(f(n)+O(1))$ है।

मान लें कि f स्पेस-कंस्ट्रक्टीबल है। स्पेस निर्धारणात्मक है।

ट्यूरिंग मशीनों सहित अनुक्रमिक कम्प्यूटेशनल मॉडल की विस्तृत विविधता के लिए, SPACE(f(n)-Big O Notation|ω(log(f(n)+n))) ⊊ SPACE(f(n)) है। यह तब भी मान्य है जब SPACE(f(n)-ω(log(f(n)+n))) को ${\mathsf {SPACE}}(f(n))$ से किसी भिन्न कम्प्यूटेशनल मॉडल का उपयोग करके परिभाषित किया गया हो क्योंकि विभिन्न मॉडल $O(\log(f(n)+n))$ स्पेस के साथ दूसरे का अनुकरण कर सकते हैं।
कुछ कम्प्यूटेशनल मॉडल के लिए, हमारे पास SPACE(f(n)-ω(1)) ⊊ SPACE(f(n)) भी है। विशेष रूप से, यह ट्यूरिंग मशीनों के लिए प्रस्तावित होता है यदि हम वर्णमाला, इनपुट टेप पर हेड्स की नंबर, वर्कटेप पर हेड्स की नंबर (वर्कटेप का उपयोग करके) को उचित बनाते हैं, एवं वर्कटेप के विज़िट किए गए भाग के लिए सीमांकक जोड़ते हैं (जिसे स्पेस उपयोग में वृद्धि के बिना चेक किया जा सकता है)। SPACE(f(n)) इस विषय पर निर्भर नहीं करता है कि वर्कटेप अनंत है या अर्ध-अनंत है। हमारे पास निश्चित नंबर में वर्कटेप भी हो सकते हैं यदि f(n) या तो प्रति-टेप स्पेस उपयोग देने वाला स्पेस कंस्ट्रक्टीबल टपल है, या SPACE(f(n)-ω(log(f(n))) - कुल स्पेस उपयोग देने वाली कंस्ट्रक्टीबल नंबर है (प्रत्येक टेप की लंबाई को संग्रहीत करने के लिए ओवरहेड की गिनती नहीं है)।

प्रूफ स्पेस हायरार्की थ्योरम के प्रूफ के समान है, किन्तु दो कॉम्प्लिकेशन के साथ: सार्वभौमिक ट्यूरिंग मशीन को स्पेस-कुशल होना चाहिए, एवं विपरीत स्पेस-कुशल होना चाहिए। कोई सामान्यतः $O(\log(space))$ स्पेस ओवरहेड, एवं उचित धारणाओं के अंतर्गत, $O(1)$ स्पेस ओवरहेड (जो मशीन के सिम्युलेटेड होने पर निर्भर हो सकता है) के साथ सार्वभौमिक ट्यूरिंग मशीनों का निर्माण कर सकता है। रिवर्सल के लिए, मुख्य विषय यह है कि कैसे ज्ञात किया जाए कि सिम्युलेटेड मशीन अनंत (स्पेस-बाधित) लूप में प्रवेश करके अस्वीकार कर देती है। केवल चरणों की नंबर गिनने से स्पेस का उपयोग लगभग $f(n)$ बढ़ जाता है। संभावित रूप से एक्सपोनेंशियल टाइम वृद्धि की कीमत पर, लूप को स्पेस-एफिशिएंसी से निम्नानुसार ज्ञात किया जा सकता है:^[1]

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

यह भी निर्धारित किया जा सकता है कि क्या मशीन स्पेस सीमा से अधिक हो गई है (स्पेस सीमा के अंदर लूपिंग के विपरीत) सभी कॉन्फ़िगरेशन पर पुनरावृत्ति करके एवं परीक्षण करके (पुनः डेप्थ-फर्स्ट सर्च का उपयोग करके) कि क्या इनिशियल कॉन्फ़िगरेशन उनमें से किसी की ओर ले जाता है।

परिणाम

परिणाम 1

किन्हीं दो फंक्शन $f_{1}$ , $f_{2}:\mathbb {N} \longrightarrow \mathbb {N}$ , के लिए जहाँ $f_{1}(n)$ , $o(f_{2}(n))$ है, एवं $f_{2}$ स्पेस-कंस्ट्रक्टिबल ${\mathsf {SPACE}}(f_{1}(n))\subsetneq {\mathsf {SPACE}}(f_{2}(n))$ है,

यह परिणाम हमें विभिन्न स्पेस कॉम्प्लेक्सिटी वर्गों को भिन्न करने की सुविधा देता है। किसी भी फंक्शन $n^{k}$ के लिए किसी भी नेचुरल नंबर k के लिए स्पेस-कंस्ट्रक्टीबल है। इसलिए किन्हीं दो नेचुरल नंबर $k_{1}<k_{2}$ के लिए हम ${\mathsf {SPACE}}(n^{k_{1}})\subsetneq {\mathsf {SPACE}}(n^{k_{2}})$ प्रूफ कर सकते हैं। इस विचार को निम्नलिखित परिणाम में रियल नंबर्स के लिए बढ़ाया जा सकता है। यह पीस्पेस वर्ग के अंदर विस्तृत हायरार्की को प्रदर्शित करता है।

परिणाम 2

किन्हीं दो नॉन नेगेटिव रियल नंबर्स के लिए $a_{1}<a_{2},{\mathsf {SPACE}}(n^{a_{1}})\subsetneq {\mathsf {SPACE}}(n^{a_{2}})$ है।

परिणाम 3

NL⊊ PSPACE

प्रूफ

सैविच का थ्योरम यह प्रदर्शित करता है ${\mathsf {NL}}\subseteq {\mathsf {SPACE}}(\log ^{2}n)$ , जबकि स्पेस हायरार्की थ्योरम ${\mathsf {SPACE}}(\log ^{2}n)\subsetneq {\mathsf {SPACE}}(n)$ प्रदर्शित करता है। इसका परिणाम इस तथ्य के साथ है कि TQBF ∉ NL क्योंकि टीक्यूबीएफ पीस्पेस-पूर्ण है।

यह दिखाने के लिए नॉन-डिटरमिनिस्टिक स्पेस हायरार्की थ्योरम का उपयोग करके भी प्रूफ किया जा सकता है कि एनएल ⊊ एनपीस्पेस, और सैविच के थ्योरम का उपयोग करके यह दिखाया जा सकता है कि पीस्पेस = एनपीस्पेस होता है।

परिणाम 4

PSPACE ⊊ EXPSPACE

यह अंतिम परिणाम उन डीसीडबल प्रोब्लेम्स के अस्तित्व को प्रदर्शित करता है जो कठिन हैं। दूसरे शब्दों में, उनके डिसिशन प्रोसीजर को पोलीनोमिअल स्पेस से अधिक उपयोग करना चाहिए।

परिणाम 5

पीस्पेस में ऐसी प्रोब्लेम्स हैं जिनको सॉल्व करने के लिए आर्बिटरी रूप से बड़े घातांक की आवश्यकता होती है; इसलिए पीस्पेस, कुछ स्थिरांक k के लिए डीस्पेस(n^k) में परिवर्तित नहीं होता है।

यह भी देखें

टाइम हायरार्की थ्योरम

संदर्भ

↑ Sipser, Michael (1978). "अंतरिक्ष-बद्ध संगणनाओं को रोकना". Proceedings of the 19th Annual Symposium on Foundations of Computer Science.

Arora, Sanjeev; Barak, Boaz (2009). Computational complexity. A modern approach. Cambridge University Press. ISBN 978-0-521-42426-4. Zbl 1193.68112.
Luca Trevisan. Notes on Hierarchy Theorems. Handout 7. CS172: Automata, Computability and Complexity. U.C. Berkeley. April 26, 2004.
Viliam Geffert. Space hierarchy theorem revised. Theoretical Computer Science, volume 295, number 1–3, p. 171-187. February 24, 2003.
Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Pages 306–310 of section 9.1: Hierarchy theorems.
Papadimitriou, Christos (1993). Computational Complexity (1st ed.). Addison Wesley. ISBN 0-201-53082-1. Section 7.2: The Hierarchy Theorem, pp. 143–146.

[1] Sipser, Michael (1978). "अंतरिक्ष-बद्ध संगणनाओं को रोकना". Proceedings of the 19th Annual Symposium on Foundations of Computer Science.

[1]

@@ Line 1: / Line 1: @@
-{{short description|Both deterministic and nondeterministic machines can solve more problems given more space}}[[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल समष्टिता सिद्धांत]] में, स्पेस पदानुक्रम प्रमेय पृथक्करण परिणाम हैं जो प्रदर्शित करते हैं कि नियतात्मक एवं अन्य-नियतात्मक दोनों मशीनें कुछ प्रतिबंधों के अधीन (अस्पष्ट रूप से) अधिक समष्टि में अधिक समस्याओं का निवारण कर सकती हैं। उदाहरण के लिए, [[नियतात्मक ट्यूरिंग मशीन]] स्पेस ''n'' की अपेक्षा में स्पेस ''n'' लॉग ''n'' में अधिक [[निर्णय समस्या|निर्णय समस्याओं]] का निवारण कर सकती है। समय के लिए सीमा तक शक्तिहीन अनुरूप प्रमेय [[समय पदानुक्रम प्रमेय]] हैं।
+{{short description|Both deterministic and nondeterministic machines can solve more problems given more space}}[[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल कम्प्लेक्सिटी थ्योरी]] में, '''स्पेस हायरार्की थ्योरम''' ऐसे सेपरेशन रिजल्ट्स हैं जो प्रदर्शित करते हैं कि डेटर्मीनिस्टिक एवं नॉन-डेटर्मीनिस्टिक दोनों मशीनें कुछ कंडीशंस के अधीन (अस्पष्ट रूप से) अधिक स्पेस में अधिक प्रोब्लेम्स को सॉल्व कर सकती हैं। उदाहरण के लिए, [[नियतात्मक ट्यूरिंग मशीन|डेटर्मीनिस्टिक ट्यूरिंग मशीन]] स्पेस ''n'' की अपेक्षा स्पेस ''n'' log ''n'' में [[निर्णय समस्या|डिसिशन प्रोब्लेम्स]] को सॉल्व कर सकती है। टाइम के लिए कुछ सीमा तक वीकर एनलॉगस थेओरेम्स [[समय पदानुक्रम प्रमेय|टाइम हायरार्की थेओरेम्स]] हैं।
-पदानुक्रम प्रमेयों की नींव अंतर्ज्ञान में निहित है कि या तो अधिक समय या अधिक समष्टि के साथ अधिक गणना करने की क्षमता आती है। पदानुक्रम प्रमेयों का प्रयोग यह प्रदर्शित करने के लिए किया जाता है कि समय एवं स्थान समष्टिता वर्ग पदानुक्रम बनाते हैं जहां कठिन सीमाओं वाली वर्गों में अधिक शिथिल सीमा वाले वर्गों की अपेक्षा में कम लैंग्वेजएं होती हैं। यहां स्पेस पदानुक्रम प्रमेय को परिभाषित एवं सिद्ध करते हैं।
+हायरार्की थेओरेम्स के आधार के इंटूइशन में निहित है कि अधिक टाइम या अधिक स्पेस के साथ कंप्यूट करने की क्षमता होती है। हायरार्की थेओरेम्स का उपयोग यह प्रदर्शित करने के लिए किया जाता है कि टाइम एवं स्पेस कम्प्लेक्सिटी क्लासेज हायरार्की बनाते हैं जहां टाइटर बॉन्ड्स में अधिक रिलैक्स्ड बॉन्ड्स की अपेक्षा कम लैंग्वेजेज होती हैं। यहां स्पेस हायरार्की थ्योरम को परिभाषित एवं प्रूफ किया जाता है।
-स्पेस पदानुक्रम प्रमेय [[अंतरिक्ष-निर्माण योग्य कार्य|स्पेस-निर्माण योग्य कार्य]]ों की अवधारणा पर निर्भर करते हैं। नियतात्मक एवं अन्य-नियतात्मक स्पेस पदानुक्रम प्रमेय बताते हैं कि सभी स्पेस-निर्माण योग्य कार्यों के लिए ''f''(''n''),
+स्पेस हायरार्की थ्योरम [[अंतरिक्ष-निर्माण योग्य कार्य|स्पेस-कंस्ट्रक्टिबल फंक्शन्स]] की अवधारणा पर निर्भर करते हैं। डेटर्मीनिस्टिक एवं नॉन-डेटर्मीनिस्टिक स्पेस हायरार्की थ्योरम बताते हैं कि सभी स्पेस-कंस्ट्रक्टिबल फंक्शन्स के लिए ''f''(''n''), इस प्रकार है:
 :<math>\mathsf{SPACE}\left(o(f(n))\right) \subsetneq \mathsf{SPACE}(f(n))</math>,
-जहां SPACE का तात्पर्य [[DSPACE]] या [[NSPACE]] है, एवं {{mvar|o}} छोटे o नोटेशन को संदर्भित करता है।
+जहां स्पेस का तात्पर्य [[DSPACE|डीस्पेस]] या [[NSPACE|एनस्पेस]] है, और {{mvar|o}} छोटे o नोटेशन को रेफेर करता है।
-== कथन ==
+== स्टेटमेंट ==
-औपचारिक रूप से,  फंक्शन <math>f:\mathbb{N} \longrightarrow \mathbb{N}</math> स्पेस-निर्माण योग्य है यदि <math>f(n) \ge \log~n</math> एवं वहाँ ट्यूरिंग मशीन उपस्थित है जो फलन <math>f(n)</math> की गणना करता है  स्पेस <math>O(f(n))</math> में इनपुट <math>1^n</math> के साथ प्रारंभ करते समय करता है, जहाँ <math>1^n</math> n क्रमागत 1s की स्ट्रिंग का प्रतिनिधित्व करता है। अधिकांश सामान्य फलन जिनके साथ हम कार्य करते हैं, वे स्पेस-निर्माण योग्य हैं, जिनमें बहुपद, घातांक एवं लघुगणक सम्मिलित हैं।
+औपचारिक रूप से, फंक्शन <math>f:\mathbb{N} \longrightarrow \mathbb{N}</math> स्पेस-कंस्ट्रक्टीबल है यदि <math>f(n) \ge \log~n</math> एवं वहाँ ट्यूरिंग मशीन उपस्थित है जो फंक्शन <math>f(n)</math> की कंप्यूट स्पेस <math>O(f(n))</math> में इनपुट <math>1^n</math> के साथ प्रारंभ करते टाइम करता है, जहाँ <math>1^n</math> n क्रमागत 1s की स्ट्रिंग का प्रतिनिधित्व करता है। अधिकांश सामान्य फंक्शन जिनके साथ हम कार्य करते हैं, वे स्पेस-कंस्ट्रक्टीबल हैं, जिनमें बहुपद, घातांक एवं लघुगणक सम्मिलित हैं।
-प्रत्येक समष्टि-निर्माण योग्य फलन <math>f:\mathbb{N} \longrightarrow
+प्रत्येक स्पेस-कंस्ट्रक्टीबल फंक्शन <math>f:\mathbb{N} \longrightarrow
 \mathbb{N}</math> के लिए, वहाँ लैंग्वेज {{mvar|L}} उपस्थित है जो स्पेस <math>O(f(n))</math> में निर्णय लेने योग्य है किन्तु स्पेस <math>o(f(n))</math> में नहीं है।
-== प्रमाण ==
+== प्रूफ ==
-लक्ष्य ऐसी लैंग्वेज को परिभाषित करना है जिसे स्पेस <math>o(f(n))</math> में नहीं अपितु  <math>O(f(n))</math> में निश्चित किया जा सकता है। लैंग्वेज को इस प्रकार  L के रूप में परिभाषित किया गया है,                            <math>L = \{~ (\langle M \rangle, 10^k): M  \mbox{ uses space } \le f(|\langle M \rangle, 10^k|) \mbox{ and time } \le 2^{f(|\langle M \rangle, 10^k|)} \mbox{ and }  M  \mbox{ does not accept } (\langle M \rangle,
+गोल ऐसी लैंग्वेज को परिभाषित करना है जिसे स्पेस <math>o(f(n))</math> में नहीं अपितु <math>O(f(n))</math> में निश्चित किया जा सकता है। लैंग्वेज को L के रूप में परिभाषित किया गया है,                            <math>L = \{~ (\langle M \rangle, 10^k): M  \mbox{ uses space } \le f(|\langle M \rangle, 10^k|) \mbox{ and time } \le 2^{f(|\langle M \rangle, 10^k|)} \mbox{ and }  M  \mbox{ does not accept } (\langle M \rangle,
 ^k) ~ \}</math>
-किसी भी मशीन के लिए {{mvar|M}}  जो स्पेस <math>o(f(n))</math> में लैंग्वेज सुनिश्चित करता है, {{mvar|L}} की लैंग्वेज से कम से कम एक समष्टि पर {{mvar|M}} से भिन्न होगा अर्थात्, कुछ बड़े पर्याप्त  {{mvar|k}} के लिए, {{mvar|M}}  समष्टि का उपयोग करेगा <math>\le f(|\langle M \rangle, 10^k|)</Math> on <math>(\langle M \rangle, 10^k)</Math> और इसलिए इसके मूल्य में भिन्नता होगी।
+किसी भी मशीन {{mvar|M}} के लिए जो स्पेस <math>o(f(n))</math> में लैंग्वेज सुनिश्चित करता है, {{mvar|L}} {{mvar|M}} की लैंग्वेज से कम से कम स्पेस पर भिन्न होगा, अर्थात्, कुछ बड़े पर्याप्त {{mvar|k}} के लिए, {{mvar|M}}  स्पेस का उपयोग करेगा <math>\le f(|\langle M \rangle, 10^k|)</Math> on <math>(\langle M \rangle, 10^k)</Math> और इसलिए इसके मूल्य में भिन्नता होगी।
-दूसरी ओर, {{mvar|L}}, <math>\mathsf{SPACE}(f(n))</math>में है। लैंग्वेज सुनिश्चित करने के लिए एल्गोरिदम {{mvar|L}} इस प्रकार है:
+दूसरी ओर, {{mvar|L}}, <math>\mathsf{SPACE}(f(n))</math>में है। लैंग्वेज {{mvar|L}} सुनिश्चित करने के लिए एल्गोरिदम इस प्रकार है:
-# इनपुट {{mvar|x}} पर, स्पेस-निर्माणशीलता का उपयोग करके <math>f(|x|)</math> की गणना की जाती है, एवं <math>f(|x|)</math> टेप की कोशिकाएँ को चिह्नित किया जाता है, जब भी <math>f(|x|)</math> कोशिकाएँ अधिक प्रयोग करने का प्रयास किया जाता है तो इसे अस्वीकार कर दिया जाता है।
+# इनपुट {{mvar|x}} पर, <math>f(|x|)</math> स्पेस-निर्माणशीलता का उपयोग और मार्क ऑफ करके कंप्यूट की जाती है, एवं <math>f(|x|)</math> टेप की सेल को चिह्नित किया जाता है, जब भी इससे अधिक प्रयोग करने का प्रयास किया जाता है तो <math>f(|x|)</math>सेल इसे अस्वीकार कर देती है।
-# यदि {{mvar|x}}, <math>\langle M \rangle, 10^k</math> रूप का नहीं है  कुछ TM के लिए {{mvar|M}}, अस्वीकार किया जाता है।
+# यदि {{mvar|x}}, <math>\langle M \rangle, 10^k</math> का स्वरूप नहीं है, तो कुछ TM के लिए {{mvar|M}}, अस्वीकार किया जाता है।
-# अनुकरण करें {{mvar|M}} इनपुट {{mvar|x}} पर अधिक से अधिक <math>2^{f(|x|)}</math>चरण के लिए ( <math>f(|x|)</math> स्पेस का उपयोग करके)। यदि सिमुलेशन <math>f(|x|)</math> समष्टि से अधिक या उससे अधिक <math>2^{f(|x|)}</math> संचालन का उपयोग करने का प्रयास करता है तो इसे अस्वीकार कर दिया जाता है।
+# अधिक से अधिक इनपुट {{mvar|x}} पर {{mvar|M}} का अनुकरण करता है, <math>2^{f(|x|)}</math>चरण ( <math>f(|x|)</math> स्पेस का उपयोग करके) है। यदि सिमुलेशन <math>f(|x|)</math> स्पेस से अधिक या उससे अधिक <math>2^{f(|x|)}</math> ऑपरेशन का उपयोग करने का प्रयास करता है तो इसे अस्वीकार कर दिया जाता है।
-# यदि इस अनुकरण के समय {{mvar|M}} ने {{mvar|x}} को स्वीकार कर लिया है, तो तो इसे अस्वीकार अन्यथा स्वीकार कर लिया जाता है
+# यदि इस अनुकरण के टाइम {{mvar|M}}  ने {{mvar|x}} को स्वीकार कर लिया है, तो इसे अस्वीकार अन्यथा स्वीकार कर लिया जाता है।
-चरण 3 पर ध्यान दें: निष्पादन यहीं तक सीमित है <math>2^{f(|x|)}</math> मामले से बचने के लिए कदम जहां {{mvar|M}} इनपुट पर रुकता नहीं है {{mvar|x}}. यानी मामला कहां है {{mvar|M}} का ही समष्टि लेता है <math>O(f(x))</math> आवश्यकतानुसार, किन्तु अनंत समय तक चलता है।
+चरण 3 पर ध्यान दें: निष्पादन यहीं तक सीमित है, उस स्थिति से बचने के लिए  <math>2^{f(|x|)}</math>चरण जहां {{mvar|M}}  इनपुट {{mvar|x}} पर नहीं रुकता है। अर्थात्, वह स्थिति जहाँ {{mvar|M}} केवल स्थान का उपभोग करता है। <math>O(f(x))</math> आवश्यकतानुसार, किन्तु अनंत टाइम तक उपयोग होता है।
-उपरोक्त प्रमाण PSPACE के मामले में मान्य है, किन्तु NPSPACE के मामले में कुछ बदलाव करने की आवश्यकता है। महत्वपूर्ण बिंदु यह है कि  नियतात्मक टीएम पर, स्वीकृति एवं अस्वीकृति को उलटा किया जा सकता है (चरण 4 के लिए महत्वपूर्ण),  अन्य-नियतात्मक मशीन पर यह संभव नहीं है।<br>
+उपरोक्त प्रूफ पीस्पेस की स्थिति में मान्य है, किन्तु एनपीस्पेस की स्थिति में कुछ परिवर्तन करने की आवश्यकता है। महत्वपूर्ण बिंदु यह है कि नियतात्मक TM पर, स्वीकृति एवं अस्वीकृति को विपरीत किया जा सकता है (चरण 4 के लिए महत्वपूर्ण), अन्य-नियतात्मक मशीन पर यह संभव नहीं है।
+एनपीस्पेस की स्थिति में, {{mvar|L}} को पुनः परिभाषित करने की आवश्यकता है:
-एनपीस्पेस के मामले के लिए, {{mvar|L}} को पहले पुनः परिभाषित करने की आवश्यकता है:
-<ब्लॉककोट>
 <math>L = \{~ (\langle M \rangle, 10^k): M  \mbox{ uses space } \le f(|\langle M \rangle, 10^k|)  \mbox{ and }  M  \mbox{ accepts } (\langle M \rangle,
 ^k) ~ \}</math>
-</ब्लॉककोट>
-अब, स्वीकार करने के लिए एल्गोरिदम को बदलने की जरूरत है {{mvar|L}} चरण 4 को संशोधित करके:
+अब, चरण 4 को संशोधित करके {{mvar|L}} को स्वीकार करने के लिए एल्गोरिदम को परिवर्तित करने की आवश्यकता है:
-* यदि {{mvar|M}} को स्वीकृत {{mvar|x}} इस अनुकरण के समय, फिर स्वीकार करें; अन्यथा, अस्वीकार करें.
+* यदि इस अनुकरण के टाइम {{mvar|M}}  ने  {{mvar|x}} को स्वीकार कर लिया है, तो स्वीकार करें; अन्यथा, अस्वीकार करें।
+{{mvar|L}} का उपयोग TM द्वारा <math>o(f(n))</math> का उपयोग नहीं किया जा सकता है। यह मानते हुए कि {{mvar|L}} का निर्णय कुछ TM {{mvar|M}} उपयोग करके किया जा सकता है <math>o(f(n))</math> सेल एवं इमरमैन-स्ज़ेलेपीसीसेनी थ्योरम का अनुसरण करते हुए, <math>\overline L</math> को TM (जिसे <math>\overline M</math>कहा जाता है) द्वारा <math>o(f(n))</math> सेल का उपयोग करके भी निर्धारित किया जा सकता है। यहाँ विरोधाभास है, इसलिए धारणा असत्य होनी चाहिए:
+# यदि <math>w = (\langle \overline M \rangle, 10^k)</math> (कुछ बड़े पर्याप्त {{mvar|k}} के लिए) <math>\overline L</math> में नहीं है इसलिए {{mvar|M}}  इसे स्वीकार करेगा, इसलिए <math>\overline M</math> {{mvar|w}} को अस्वीकार करता है, इसलिए {{mvar|w}} <math>\overline L</math> में है (विरोधाभास)।
+# यदि <math>w = (\langle \overline M \rangle, 10^k)</math> (कुछ बड़े पर्याप्त {{mvar|k}} के लिए) <math>\overline L</math> में है इसलिए {{mvar|M}}  इसे अस्वीकार कर देगा <math>\overline M</math> {{mvar|w}} को स्वीकार करता है, इसलिए {{mvar|w}}, <math>\overline L</math> में नहीं है  (विरोधाभास)।
-{{mvar|L}} का उपयोग टीएम द्वारा सुनिश्चित नहीं किया जा सकता <math>o(f(n))</math> कोशिकाएं. यह मानते हुए {{mvar|L}} कुछ टीएम द्वारा निर्णय लिया जा सकता है {{mvar|M}} का उपयोग करना <math>o(f(n))</math> कोशिकाएँ, एवं इमरमैन-स्ज़ेलेपीसीसेनी प्रमेय का अनुसरण करते हुए, <math>\overline L</math> इसे टीएम (जिसे कहा जाता है) द्वारा भी निर्धारित किया जा सकता है <math>\overline M</math>) का उपयोग करना <math>o(f(n))</math> कोशिकाएं. यहाँ विरोधाभास है, इसलिए धारणा झूठी होनी चाहिए:
+== कम्पेरिज़न और इम्प्रोवेमेन्ट्स ==
-# यदि <math>w = (\langle \overline M \rangle, 10^k)</math> (कुछ बड़े वर्गों के लिए {{mvar|k}}) इसमें नहीं है <math>\overline L</math> तब {{mvar|M}} इसलिए इसे स्वीकार करेंगे <math>\overline M</math> अस्वीकृत {{mvar|w}}, इसलिए {{mvar|w}} में है <math>\overline L</math> (विरोधाभास)।
-# यदि <math>w = (\langle \overline M \rangle, 10^k)</math> (कुछ बड़े वर्गों के लिए {{mvar|k}}) में है <math>\overline L</math> तब {{mvar|M}} इसलिए इसे अस्वीकार कर देंगे <math>\overline M</math> स्वीकार {{mvar|w}}, इसलिए {{mvar|w}} इसमें नहीं है <math>\overline L</math> (विरोधाभास)।
-== अपेक्षा एवं सुधार ==
+स्पेस हायरार्की थ्योरम कई विषयों में अनुरूप टाइम हायरार्की थेओरेम्स से अधिक सशक्त है:
+* इसके लिए केवल s(n) को कम से कम n के अतिरिक्त कम से कम log n होना आवश्यक है।
+* यह किसी भी स्पर्शोन्मुख अंतर के साथ वर्गों को भिन्न कर सकता है, जबकि टाइम हायरार्की थ्योरम के लिए उन्हें लोगरिथम फैक्टर द्वारा भिन्न करने की आवश्यकता होती है।
+* इसके लिए फंक्शन को टाइम-कंस्ट्रक्टीबल नहीं अपितु स्पेस-कंस्ट्रक्टीबल होना आवश्यक है।
-स्पेस पदानुक्रम प्रमेय कई मायनों में अनुरूप समय पदानुक्रम प्रमेयों से अधिक मजबूत है:
+टाइम की अपेक्षा में स्पेस में वर्गों को भिन्न करना सरल लगता है। वास्तव में, जबकि टाइम हायरार्की थ्योरम ने अपनी स्थापना के पश्चात से उल्लेखनीय सुधार देखा है, नॉन डिटरमिनिस्टिक स्पेस हायरार्की थ्योरम में कम से कम महत्वपूर्ण सुधार देखा गया है जिसे [[ विलियम गेफ़र्ट |विलियम गेफ़र्ट]] ने अपने 2003 के पेपर स्पेस हायरार्की थ्योरम में संशोधित किया है। इस पेपर ने थ्योरम के कई सामान्यीकरण किये है:
-* इसके लिए केवल s(n) को कम से कम n के बजाय कम से कम लॉग n होना आवश्यक है।
-* यह किसी भी स्पर्शोन्मुख अंतर के साथ वर्गों को अलग कर सकता है, जबकि समय पदानुक्रम प्रमेय के लिए उन्हें लघुगणकीय कारक द्वारा अलग करने की आवश्यकता होती है।
-* इसके लिए केवल फलन को समष्टि-निर्माण योग्य होना आवश्यक है, समय-निर्माण योग्य नहीं।
-समय की अपेक्षा में स्पेस में कक्षाओं को अलग करना आसान लगता है। वास्तव में, जबकि समय पदानुक्रम प्रमेय ने अपनी स्थापना के बाद से थोड़ा उल्लेखनीय सुधार देखा है, अन्य-नियतात्मक स्पेस पदानुक्रम प्रमेय में कम से कम  महत्वपूर्ण सुधार देखा गया है जिसे [[ विलियम गेफ़र्ट ]] ने अपने 2003 के पेपर स्पेस पदानुक्रम प्रमेय में संशोधित किया है। इस पेपर ने प्रमेय के कई सामान्यीकरण किये:
+* यह स्पेस-निर्माण योग्यता की आवश्यकता को शिथिल करता है। केवल संघ वर्गों {{tmath|\mathsf{DSPACE}(O(s(n))}} एवं {{tmath|\mathsf{DSPACE}(o(s(n))}} को भिन्न करने के अतिरिक्त यह  {{tmath|\mathsf{DSPACE}(f(n))}} से {{tmath|\mathsf{DSPACE}(g(n))}} को भिन्न करता है, जहाँ {{tmath|f(n)}} आर्बिटरी है {{tmath|O(s(n))}} फंक्शन एवं g(n) कंप्यूट योग्य {{tmath|o(s(n))}} फंक्शन है। इन फंक्शन को स्पेस-कंस्ट्रक्टीबल या मोनोटोन बढ़ाने की आवश्यकता नहीं है।
+* यह यूनरी लैंग्वेज या टैली लैंग्वेज की पहचान करता है, जो वर्ग में है किन्तु दूसरे में नहीं है। मूल थ्योरम में, भिन्न करने वाली लैंग्वेज आर्बिटरी थी।
+* इसकी आवश्यकता नहीं है, {{tmath|s(n)}} कम से कम log n होना चाहिए; यह कोई भी अन्य-नियतात्मक रूप से पूर्णतः स्पेस-कंस्ट्रक्टीबल कार्य हो सकता है।
-* यह स्पेस-निर्माण योग्यता की आवश्यकता को शिथिल करता है। केवल संघ वर्गों को अलग करने के बजाय {{tmath|\mathsf{DSPACE}(O(s(n))}} एवं {{tmath|\mathsf{DSPACE}(o(s(n))}}, यह अलग हो जाता है {{tmath|\mathsf{DSPACE}(f(n))}} से {{tmath|\mathsf{DSPACE}(g(n))}} जहाँ {{tmath|f(n)}}  मनमाना है {{tmath|O(s(n))}} फलन एवं g(n)  गणना योग्य फलन है {{tmath|o(s(n))}} फंक्शन। इन कार्यों को समष्टि-निर्माण योग्य या यहां तक कि मोनोटोन बढ़ाने की आवश्यकता नहीं है।
+==रिफाइनमेंट स्पेस हायरार्की ==
-* यह  यूनरी लैंग्वेज या टैली लैंग्वेज की पहचान करता है, जो  वर्ग में है किन्तु दूसरे में नहीं। मूल प्रमेय में, अलग करने वाली लैंग्वेज मनमानी थी।
-* इसकी आवश्यकता नहीं है {{tmath|s(n)}} कम से कम लॉग एन होना; यह कोई भी अन्य-नियतात्मक रूप से पूर्णतः स्पेस-निर्माण योग्य कार्य हो सकता है।
-==स्पेस पदानुक्रम का परिशोधन==
+यदि स्पेस को वर्णमाला के आकार पर विचार किए बिना उपयोग की गई सेल की नंबर के रूप में मापा जाता है, तो {{tmath|1=\mathsf{SPACE}(f(n)) = \mathsf{SPACE}(O(f(n)))}} होता है, क्योंकि कोई भी बड़े वर्णमाला पर स्विच करके किसी भी रैखिक कम्प्रेशन को प्राप्त कर सकता है। चूँकि, बिट्स में स्पेस को मापने से, नियतात्मक स्पेस के लिए अधिक तीव्र पृथक्करण प्राप्त किया जा सकता है। गुणात्मक स्थिरांक तक परिभाषित होने के अतिरिक्त, स्पेस को अब योगात्मक स्थिरांक तक परिभाषित किया गया है। चूँकि, क्योंकि एक्सटर्नल स्पेस की किसी भी स्थिर मात्रा को कंटेंट्स को आंतरिक स्थिति में संग्रहीत करके बचाया जा सकता है, हमारे पास अभी भी {{tmath|1=\mathsf{SPACE}(f(n)) = \mathsf{SPACE}(f(n)+O(1))}}है।
-यदि समष्टि को वर्णमाला के आकार की परवाह किए बिना उपयोग की गई कोशिकाओं की संख्या के रूप में मापा जाता है, तो {{tmath|1=\mathsf{SPACE}(f(n)) = \mathsf{SPACE}(O(f(n)))}} क्योंकि कोई भी बड़े वर्णमाला पर स्विच करके किसी भी रैखिक संपीड़न को प्राप्त कर सकता है। हालाँकि, बिट्स में समष्टि को मापने से, नियतात्मक समष्टि के लिए बहुत तेज पृथक्करण प्राप्त किया जा सकता है। गुणात्मक स्थिरांक तक परिभाषित होने के बजाय, स्पेस को अब  योगात्मक स्थिरांक तक परिभाषित किया गया है। हालाँकि, क्योंकि बाहरी समष्टि की किसी भी स्थिर मात्रा को सामग्री को आंतरिक स्थिति में संग्रहीत करके बचाया जा सकता है, हमारे पास अभी भी है {{tmath|1=\mathsf{SPACE}(f(n)) = \mathsf{SPACE}(f(n)+O(1))}}.
+मान लें कि f स्पेस-कंस्ट्रक्टीबल है। स्पेस निर्धारणात्मक है।
+* ट्यूरिंग मशीनों सहित अनुक्रमिक कम्प्यूटेशनल मॉडल की विस्तृत विविधता के लिए, SPACE(f(n)-Big O Notation|ω(log(f(n)+n))) ⊊ SPACE(f(n)) है। यह तब भी मान्य है जब SPACE(f(n)-ω(log(f(n)+n))) को {{tmath|\mathsf{SPACE}(f(n))}} से किसी भिन्न कम्प्यूटेशनल मॉडल का उपयोग करके परिभाषित किया गया हो क्योंकि विभिन्न मॉडल  {{tmath|O(\log(f(n)+n))}} स्पेस के साथ दूसरे का अनुकरण कर सकते हैं।
+* कुछ कम्प्यूटेशनल मॉडल के लिए, हमारे पास SPACE(f(n)-ω(1)) ⊊ SPACE(f(n)) भी है। विशेष रूप से, यह ट्यूरिंग मशीनों के लिए प्रस्तावित होता है यदि हम वर्णमाला, इनपुट टेप पर हेड्स की नंबर, वर्कटेप पर हेड्स की नंबर (वर्कटेप का उपयोग करके) को उचित बनाते हैं, एवं वर्कटेप के विज़िट किए गए भाग के लिए सीमांकक जोड़ते हैं (जिसे स्पेस उपयोग में वृद्धि के बिना चेक किया जा सकता है)। SPACE(f(n)) इस विषय पर निर्भर नहीं करता है कि वर्कटेप अनंत है या अर्ध-अनंत है। हमारे पास निश्चित नंबर में वर्कटेप भी हो सकते हैं यदि f(n) या तो प्रति-टेप स्पेस उपयोग देने वाला स्पेस कंस्ट्रक्टीबल टपल है, या  SPACE(f(n)-ω(log(f(n))) - कुल स्पेस उपयोग देने वाली कंस्ट्रक्टीबल नंबर है (प्रत्येक टेप की लंबाई को संग्रहीत करने के लिए ओवरहेड की गिनती नहीं है)।
-मान लें कि f स्पेस-निर्माण योग्य है। स्पेस नियतिवादी है.
+प्रूफ स्पेस हायरार्की थ्योरम के प्रूफ के समान है, किन्तु दो कॉम्प्लिकेशन के साथ: सार्वभौमिक ट्यूरिंग मशीन को स्पेस-कुशल होना चाहिए, एवं विपरीत स्पेस-कुशल होना चाहिए। कोई सामान्यतः {{tmath|O(\log(space))}} स्पेस ओवरहेड, एवं उचित धारणाओं के अंतर्गत, {{tmath|O(1)}} स्पेस ओवरहेड (जो मशीन के सिम्युलेटेड होने पर निर्भर हो सकता है) के साथ सार्वभौमिक ट्यूरिंग मशीनों का निर्माण कर सकता है। रिवर्सल के लिए, मुख्य विषय यह है कि कैसे ज्ञात किया जाए कि सिम्युलेटेड मशीन अनंत (स्पेस-बाधित) लूप में प्रवेश करके अस्वीकार कर देती है। केवल चरणों की नंबर गिनने से स्पेस का उपयोग लगभग {{tmath|f(n)}} बढ़ जाता है। संभावित रूप से एक्सपोनेंशियल टाइम वृद्धि की कीमत पर, लूप को स्पेस-एफिशिएंसी से निम्नानुसार ज्ञात किया जा सकता है:<ref>{{cite conference | first = Michael | last = Sipser | title = अंतरिक्ष-बद्ध संगणनाओं को रोकना| book-title = Proceedings of the 19th Annual Symposium on Foundations of Computer Science | date = 1978}}</ref>
-* ट्यूरिंग मशीनों सहित अनुक्रमिक कम्प्यूटेशनल मॉडल की  विस्तृत विविधता के लिए, SPACE(f(n)-Big O Notation|ω(log(f(n)+n))) ⊊ SPACE(f(n))। यह तब भी मान्य है जब SPACE(f(n)-ω(log(f(n)+n))) को किसी भिन्न कम्प्यूटेशनल मॉडल का उपयोग करके परिभाषित किया गया हो {{tmath|\mathsf{SPACE}(f(n))}} क्योंकि विभिन्न मॉडल -दूसरे का अनुकरण कर सकते हैं {{tmath|O(\log(f(n)+n))}} स्पेस उपरि.
-* कुछ कम्प्यूटेशनल मॉडल के लिए, हमारे पास SPACE(f(n)-ω(1)) ⊊ SPACE(f(n)) भी है। विशेष रूप से, यह ट्यूरिंग मशीनों के लिए लागू होता है यदि हम वर्णमाला, इनपुट टेप पर हेड्स की संख्या, वर्कटेप पर हेड्स की संख्या (ल वर्कटेप का उपयोग करके) को ठीक करते हैं, एवं वर्कटेप के विज़िट किए गए हिस्से के लिए सीमांकक जोड़ते हैं (जिसे स्पेस उपयोग में वृद्धि के बिना चेक किया जा सकता है)। SPACE(f(n)) इस बात पर निर्भर नहीं करता है कि वर्कटेप अनंत है या अर्ध-अनंत। हमारे पास निश्चित संख्या में वर्कटेप भी हो सकते हैं यदि f(n) या तो प्रति-टेप स्पेस उपयोग देने वाला  SPACE रचनात्मक टपल है, या  SPACE(f(n)-ω(log(f(n))) - कुल स्पेस उपयोग देने वाली रचनात्मक संख्या है (प्रत्येक टेप की लंबाई को संग्रहीत करने के लिए ओवरहेड की गिनती नहीं)।
-प्रमाण स्पेस पदानुक्रम प्रमेय के प्रमाण के समान है, किन्तु दो समष्टिताओं के साथ: सार्वभौमिक ट्यूरिंग मशीन को स्पेस-कुशल होना चाहिए, एवं उलटा समष्टि-कुशल होना चाहिए। कोई आम तौर पर सार्वभौमिक ट्यूरिंग मशीनों का निर्माण कर सकता है {{tmath|O(\log(space))}} समष्टि ओवरहेड, एवं उचित धारणाओं के तहत, बस {{tmath|O(1)}} स्पेस ओवरहेड (जो मशीन के सिम्युलेटेड होने पर निर्भर हो सकता है)। उत्क्रमण के लिए, मुख्य मुद्दा यह है कि कैसे पता लगाया जाए कि सिम्युलेटेड मशीन  अनंत (समष्टि-बाधित) लूप में प्रवेश करके अस्वीकार कर देती है। केवल उठाए गए कदमों की संख्या गिनने से जगह की खपत लगभग बढ़ जाएगी {{tmath|f(n)}}. संभावित रूप से घातीय समय वृद्धि की कीमत पर, लूप को समष्टि-कुशलता से निम्नानुसार पता लगाया जा सकता है:<ref>{{cite conference | first = Michael | last = Sipser | title = अंतरिक्ष-बद्ध संगणनाओं को रोकना| book-title = Proceedings of the 19th Annual Symposium on Foundations of Computer Science | date = 1978}}</ref>
+सब समाप्त करने के लिए मशीन को संशोधित करते है एवं सफल होने पर स्पेसिफिक कॉन्फ़िगरेशन A पर जाते है। यह निर्धारित करने के लिए डेप्थ-फर्स्ट सर्च का उपयोग करें कि क्या A इनिशियल कॉन्फ़िगरेशन से बाउंड स्पेस में पहुंच योग्य है। सर्च A से प्रारम्भ होती है एवं उन कॉन्फ़िगरेशनों पर जाती है जो A की ओर ले जाती हैं। डेटर्मिनिस्म के कारण, यह लूप में जाए बिना ही किया जा सकता है।
-सब कुछ मिटाने के लिए मशीन को संशोधित करें एवं सफल होने पर  विशिष्ट कॉन्फ़िगरेशन ए पर जाएं। यह निर्धारित करने के लिए गहराई-प्रथम खोज का उपयोग करें कि क्या ए प्रारंभिक कॉन्फ़िगरेशन से बंधे समष्टि में पहुंच योग्य है। खोज ए से शुरू होती है एवं उन कॉन्फ़िगरेशनों पर जाती है जो ए की ओर ले जाती हैं। नियतिवाद के कारण, यह  लूप में जाए बिना ही किया जा सकता है।
-यह भी निर्धारित किया जा सकता है कि क्या मशीन स्पेस सीमा से अधिक हो गई है (स्पेस सीमा के भीतर लूपिंग के विपरीत) सभी कॉन्फ़िगरेशन पर पुनरावृत्ति करके स्पेस सीमा से अधिक हो गई है एवं जांच कर रही है (फिर से [[गहराई-पहली खोज]] का उपयोग करके) कि क्या प्रारंभिक कॉन्फ़िगरेशन उनमें से किसी की ओर ले जाता है।
+यह भी निर्धारित किया जा सकता है कि क्या मशीन स्पेस सीमा से अधिक हो गई है (स्पेस सीमा के अंदर लूपिंग के विपरीत) सभी कॉन्फ़िगरेशन पर पुनरावृत्ति करके एवं परीक्षण करके (पुनः [[गहराई-पहली खोज|डेप्थ-फर्स्ट सर्च]] का उपयोग करके) कि क्या इनिशियल कॉन्फ़िगरेशन उनमें से किसी की ओर ले जाता है।
 == परिणाम ==
@@ Line 75: / Line 77: @@
 === परिणाम 1 ===
-किन्हीं दो कार्यों के लिए <math>f_1</math>, <math>f_2: \mathbb{N} \longrightarrow
+किन्हीं दो फंक्शन  <math>f_1</math>, <math>f_2: \mathbb{N} \longrightarrow
-\mathbb{N}</math>, जहाँ <math>f_1(n)</math> है <math>o(f_2(n))</math> एवं <math>f_2</math> स्पेस-निर्माण योग्य है, <math>\mathsf{SPACE}(f_1(n)) \subsetneq \mathsf{SPACE}(f_2(n))</math>.
+\mathbb{N}</math>, के लिए जहाँ <math>f_1(n)</math>, <math>o(f_2(n))</math> है, एवं <math>f_2</math> स्पेस-कंस्ट्रक्टिबल <math>\mathsf{SPACE}(f_1(n)) \subsetneq \mathsf{SPACE}(f_2(n))</math> है,
-यह परिणाम हमें विभिन्न स्पेस समष्टिता वर्गों को अलग करने की सुविधा देता है।
+यह परिणाम हमें विभिन्न स्पेस कॉम्प्लेक्सिटी वर्गों को भिन्न करने की सुविधा देता है। किसी भी फंक्शन <math>n^k</math> के लिए किसी भी नेचुरल नंबर k के लिए स्पेस-कंस्ट्रक्टीबल है। इसलिए किन्हीं दो नेचुरल नंबर <math>k_1 < k_2</math> के लिए हम <math>\mathsf{SPACE}(n^{k_1}) \subsetneq \mathsf{SPACE}(n^{k_2})</math> प्रूफ कर सकते हैं। इस विचार को निम्नलिखित परिणाम में रियल नंबर्स के लिए बढ़ाया जा सकता है। यह पीस्पेस वर्ग के अंदर विस्तृत हायरार्की को प्रदर्शित करता है।
-किसी भी फंक्शन के लिए <math>n^k</math> किसी भी प्राकृतिक के लिए समष्टि-निर्माण योग्य है
-संख्या क. इसलिए किन्हीं दो प्राकृत संख्याओं के लिए <math>k_1 < k_2</math> हम कर सकते हैं
-सिद्ध करना <math>\mathsf{SPACE}(n^{k_1}) \subsetneq \mathsf{SPACE}(n^{k_2})</math>. इस विचार को निम्नलिखित परिणाम में वास्तविक संख्याओं के लिए बढ़ाया जा सकता है। यह PSPACE वर्ग के भीतर विस्तृत पदानुक्रम को प्रदर्शित करता है।
 === परिणाम 2 ===
-किन्हीं दो अऋणात्मक वास्तविक संख्याओं के लिए <math>a_1 < a_2, \mathsf{SPACE}(n^{a_1})
+किन्हीं दो नॉन नेगेटिव रियल नंबर्स के लिए <math>a_1 < a_2, \mathsf{SPACE}(n^{a_1})
-\subsetneq \mathsf{SPACE}(n^{a_2})</math>.
+\subsetneq \mathsf{SPACE}(n^{a_2})</math> है।
 === परिणाम 3 ===
-:[[एनएल (जटिलता)|एनएल (समष्टिता)]] ⊊ [[पीस्पेस]]।
+:[[एनएल (जटिलता)|NL]]⊊ [[पीस्पेस|PSPACE]]
-==== प्रमाण ====
+==== प्रूफ ====
-सैविच का प्रमेय यह दर्शाता है <math>\mathsf{NL} \subseteq \mathsf{SPACE}(\log^2n)</math>, जबकि स्पेस पदानुक्रम प्रमेय यह दर्शाता है <math>\mathsf{SPACE}(\log^2n) \subsetneq \mathsf{SPACE}(n)</math>. परिणाम इस तथ्य के साथ-साथ यह है कि TQBF ∉ NL
+सैविच का थ्योरम यह प्रदर्शित करता है <math>\mathsf{NL} \subseteq \mathsf{SPACE}(\log^2n)</math>, जबकि स्पेस हायरार्की थ्योरम <math>\mathsf{SPACE}(\log^2n) \subsetneq \mathsf{SPACE}(n)</math> प्रदर्शित करता है। इसका परिणाम इस तथ्य के साथ है कि TQBF ∉ NL क्योंकि टीक्यूबीएफ पीस्पेस-पूर्ण है।
-चूँकि TQBF PSPACE-पूर्ण है।
-यह दिखाने के लिए अन्य-नियतात्मक स्पेस पदानुक्रम प्रमेय का उपयोग करके भी सिद्ध किया जा सकता है कि एनएल ⊊ एनपीपीएसीई, एवं सैविच के प्रमेय का उपयोग करके यह दिखाया जा सकता है कि पीएसपीएसीई = एनपीपीएसीई।
+यह दिखाने के लिए नॉन-डिटरमिनिस्टिक स्पेस हायरार्की थ्योरम का उपयोग करके भी प्रूफ किया जा सकता है कि एनएल ⊊ एनपीस्पेस, और सैविच के थ्योरम का उपयोग करके यह दिखाया जा सकता है कि पीस्पेस = एनपीस्पेस होता है।
 === परिणाम 4 ===
-:पीएसस्पेस ⊊[[एक्सस्पेस|्सस्पेस]]।
+:PSPACE ⊊ [[एक्सस्पेस|EXPSPACE]]
-यह अंतिम परिणाम उन निर्णायक समस्याओं के अस्तित्व को दर्शाता है जो कठिन हैं। दूसरे शब्दों में, उनकी निर्णय प्रक्रियाओं को बहुपद समष्टि से अधिक का उपयोग करना चाहिए।
+यह अंतिम परिणाम उन डीसीडबल प्रोब्लेम्स के अस्तित्व को प्रदर्शित करता है जो कठिन हैं। दूसरे शब्दों में, उनके डिसिशन प्रोसीजर को पोलीनोमिअल स्पेस से अधिक उपयोग करना चाहिए।
 === परिणाम 5 ===
-में समस्याएं हैं {{sans-serif|PSPACE}} हल करने के लिए मनमाने ढंग से बड़े घातांक की आवश्यकता होती है; इसलिए {{sans-serif|PSPACE}} पतन नहीं होता {{sans-serif|DSPACE}}(एन<sup>k</sup>) कुछ स्थिरांक के लिए k.
+{{sans-serif|पीस्पेस}} में ऐसी प्रोब्लेम्स हैं जिनको सॉल्व करने के लिए आर्बिटरी रूप से बड़े घातांक की आवश्यकता होती है; इसलिए {{sans-serif|पीस्पेस}}, कुछ स्थिरांक k के लिए {{sans-serif|डीस्पेस}}(n<sup>k</sup>) में परिवर्तित नहीं होता है।
 == यह भी देखें ==
-* समय पदानुक्रम प्रमेय
+* टाइम हायरार्की थ्योरम
 == संदर्भ ==
@@ Line 126: / Line 124: @@
 [[Category: Machine Translated Page]]
 [[Category:Created On 25/07/2023]]
+[[Category:Vigyan Ready]]

Anonymous

Search

समष्टि पदानुक्रम प्रमेय: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 22:36, 2 February 2024

Contents

स्टेटमेंट

प्रूफ

कम्पेरिज़न और इम्प्रोवेमेन्ट्स

रिफाइनमेंट स्पेस हायरार्की