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

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

पदानुक्रम प्रमेयों की नींव अंतर्ज्ञान में निहित है कि या तो अधिक समय या अधिक समष्टि के साथ अधिक गणना करने की क्षमता आती है। पदानुक्रम प्रमेयों का प्रयोग यह प्रदर्शित करने के लिए किया जाता है कि समय एवं स्थान समष्टिता वर्ग पदानुक्रम बनाते हैं जहां कठिन सीमाओं वाली वर्गों में अधिक शिथिल सीमा वाले वर्गों की अपेक्षा में कम लैंग्वेजएं होती हैं। यहां स्पेस पदानुक्रम प्रमेय को परिभाषित एवं सिद्ध करते हैं।

स्पेस पदानुक्रम प्रमेय स्पेस-निर्माण योग्य कार्यों की अवधारणा पर निर्भर करते हैं। नियतात्मक एवं अन्य-नियतात्मक स्पेस पदानुक्रम प्रमेय बताते हैं कि सभी स्पेस-निर्माण योग्य कार्यों के लिए f(n),

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

जहां SPACE का तात्पर्य DSPACE या NSPACE है, एवं 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. अनुकरण करें M इनपुट x पर अधिक से अधिक $2^{f(|x|)}$चरण के लिए ( $f(|x|)$ स्पेस का उपयोग करके)। यदि सिमुलेशन $f(|x|)$ समष्टि से अधिक या उससे अधिक $2^{f(|x|)}$ संचालन का उपयोग करने का प्रयास करता है तो इसे अस्वीकार कर दिया जाता है।
4. यदि इस अनुकरण के समय M ने x को स्वीकार कर लिया है, तो इसे अस्वीकार अन्यथा स्वीकार कर लिया जाता है

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

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

NPSPACE के विषय के लिए, 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 के अतिरिक्त कम से कम लॉग 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)$ कम से कम लॉग एन होना चाहिए; यह कोई भी अन्य-नियतात्मक रूप से पूर्णतः स्पेस-निर्माण योग्य कार्य हो सकता है।

स्पेस पदानुक्रम का परिशोधन

यदि समष्टि को वर्णमाला के आकार की परवाह किए बिना उपयोग की गई कोशिकाओं की संख्या के रूप में मापा जाता है, तो ${\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 रचनात्मक टपल है, या SPACE(f(n)-ω(log(f(n))) - कुल स्पेस उपयोग देने वाली रचनात्मक संख्या है (प्रत्येक टेप की लंबाई को संग्रहीत करने के लिए ओवरहेड की गिनती नहीं)।

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

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

परिणाम

परिणाम 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_{1}<k_{2}$ हम कर सकते हैं सिद्ध करना ${\mathsf {SPACE}}(n^{k_{1}})\subsetneq {\mathsf {SPACE}}(n^{k_{2}})$. इस विचार को निम्नलिखित परिणाम में वास्तविक संख्याओं के लिए बढ़ाया जा सकता है। यह PSPACE वर्ग के भीतर विस्तृत पदानुक्रम को प्रदर्शित करता है।

परिणाम 2

किन्हीं दो अऋणात्मक वास्तविक संख्याओं के लिए $a_{1}<a_{2},{\mathsf {SPACE}}(n^{a_{1}})\subsetneq {\mathsf {SPACE}}(n^{a_{2}})$.

परिणाम 3

एनएल (समष्टिता) ⊊ पीस्पेस।

प्रमाण

सैविच का प्रमेय यह दर्शाता है ${\mathsf {NL}}\subseteq {\mathsf {SPACE}}(\log ^{2}n)$, जबकि स्पेस पदानुक्रम प्रमेय यह दर्शाता है ${\mathsf {SPACE}}(\log ^{2}n)\subsetneq {\mathsf {SPACE}}(n)$. परिणाम इस तथ्य के साथ-साथ यह है कि TQBF ∉ NL चूँकि TQBF PSPACE-पूर्ण है।

यह दिखाने के लिए अन्य-नियतात्मक स्पेस पदानुक्रम प्रमेय का उपयोग करके भी सिद्ध किया जा सकता है कि एनएल ⊊ एनपीपीएसीई, एवं सैविच के प्रमेय का उपयोग करके यह दिखाया जा सकता है कि पीएसपीएसीई = एनपीपीएसीई।

परिणाम 4

पीएसस्पेस ⊊्सस्पेस।

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

परिणाम 5

में समस्याएं हैं PSPACE हल करने के लिए मनमाने ढंग से बड़े घातांक की आवश्यकता होती है; इसलिए PSPACE पतन नहीं होता DSPACE(एन^k) कुछ स्थिरांक के लिए 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.