समष्टि पदानुक्रम प्रमेय

कम्प्यूटेशनल कम्प्लेक्सिटी थ्योरी में, स्पेस हायरार्की थ्योरम ऐसे सेपरेशन रिजल्ट्स हैं जो प्रदर्शित करते हैं कि डेटर्मीनिस्टिक एवं नॉन-डेटर्मीनिस्टिक दोनों मशीनें कुछ कंडीशंस के अधीन (अस्पष्ट रूप से) अधिक स्पेस में अधिक प्रोब्लेम्स को सॉल्व कर सकती हैं। उदाहरण के लिए, डेटर्मीनिस्टिक ट्यूरिंग मशीन स्पेस 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 सुनिश्चित करने के लिए एल्गोरिदम इस प्रकार है:

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

1. यदि $w=(\langle {\overline {M}}\rangle ,10^{k})$ (कुछ बड़े पर्याप्त k के लिए) ${\overline {L}}$ में नहीं है इसलिए M इसे स्वीकार करेगा, इसलिए ${\overline {M}}$ w को अस्वीकार करता है, इसलिए w ${\overline {L}}$ में है (विरोधाभास)।
2. यदि $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)$ बढ़ जाता है। संभावित रूप से एक्सपोनेंशियल टाइम वृद्धि की कीमत पर, लूप को स्पेस-एफिशिएंसी से निम्नानुसार ज्ञात किया जा सकता है:

सब समाप्त करने के लिए मशीन को संशोधित करते है एवं सफल होने पर स्पेसिफिक कॉन्फ़िगरेशन 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) में परिवर्तित नहीं होता है।

यह भी देखें

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

संदर्भ

• 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.