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

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

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

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

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

जहां SPACE का मतलब DSPACE या NSPACE है, एवं 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})$ and will therefore differ at its value.

On the other hand, L is in ${\mathsf {SPACE}}(f(n))$. भाषा तय करने के लिए एल्गोरिदम L इस प्रकार है:

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

• अगर M को स्वीकृत x इस अनुकरण के दौरान, फिर स्वीकार करें; अन्यथा, अस्वीकार करें.

L का उपयोग टीएम द्वारा तय नहीं किया जा सकता $o(f(n))$ कोशिकाएं. यह मानते हुए L कुछ टीएम द्वारा निर्णय लिया जा सकता है M का उपयोग करना $o(f(n))$ कोशिकाएँ, एवं इमरमैन-स्ज़ेलेपीसीसेनी प्रमेय का अनुसरण करते हुए, ${\overline {L}}$ इसे टीएम (जिसे कहा जाता है) द्वारा भी निर्धारित किया जा सकता है ${\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.