समष्टि पदानुक्रम प्रमेय: 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}}[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, अंतरिक्ष पदानुक्रम प्रमेय पृथक्करण परिणाम हैं जो दिखाते हैं कि नियतात्मक और गैर-नियतात्मक दोनों मशीनें कुछ शर्तों के अधीन (अस्पष्ट रूप से) अधिक स्थान में अधिक समस्याओं को हल कर सकती हैं। उदाहरण के लिए, एक [[नियतात्मक ट्यूरिंग मशीन]] अंतरिक्ष ''एन'' की तुलना में अंतरिक्ष ''एन'' लॉग ''एन'' में अधिक [[निर्णय समस्या]]ओं को हल कर सकती है। समय के लिए कुछ हद तक कमजोर अनुरूप प्रमेय [[समय पदानुक्रम प्रमेय]] हैं।
+{{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}} छोटे ओ नोटेशन को संदर्भित करता है।
+जहां स्पेस का तात्पर्य [[DSPACE|डीस्पेस]] या [[NSPACE|एनस्पेस]] है, और {{mvar|o}} छोटे o नोटेशन को रेफेर करता है।
-== कथन ==
+== स्टेटमेंट ==
-औपचारिक रूप से, एक समारोह <math>f:\mathbb{N} \longrightarrow \mathbb{N}</math> यदि अंतरिक्ष-निर्माण योग्य है <math>f(n) \ge \log~n</math> और वहाँ एक ट्यूरिंग मशीन मौजूद है
+औपचारिक रूप से, फंक्शन <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(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}} जो अंतरिक्ष में निर्णय लेने योग्य है
+\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>.
-== प्रमाण ==
+== प्रूफ ==
-लक्ष्य एक ऐसी भाषा को परिभाषित करना है जिसे अंतरिक्ष में तय किया जा सके <math>O(f(n))</math> लेकिन जगह नहीं <math>o(f(n))</math>. भाषा को इस प्रकार परिभाषित किया गया है {{mvar|L}}:
+गोल ऐसी लैंग्वेज को परिभाषित करना है जिसे स्पेस <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>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> and will therefore differ at its value.
+किसी भी मशीन {{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> और इसलिए इसके मूल्य में भिन्नता होगी।
-On the other hand, {{mvar|L}} is in <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> कुछ टीएम के लिए {{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 87: / 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 132: / Line 118: @@
 * {{cite book | first=Christos | last=Papadimitriou | author-link = Christos Papadimitriou | year = 1993 | title = Computational Complexity | publisher = Addison Wesley | edition = 1st  | isbn = 0-201-53082-1}} Section 7.2: The Hierarchy Theorem, pp.&nbsp;143&ndash;146.
-<!-- Need to add original source here -->
 [[Category: प्रमाण युक्त लेख]] [[Category: संरचनात्मक जटिलता सिद्धांत]] [[Category: कम्प्यूटेशनल जटिलता सिद्धांत में प्रमेय]]
@@ Line 139: / 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

स्टेटमेंट

प्रूफ

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

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