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

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

पदानुक्रम प्रमेयों की नींव अंतर्ज्ञान में निहित है अधिक समय या अधिक स्थान के साथ अधिक गणना करने की क्षमता आती है फ़ंक्शन (या अधिक भाषाएँ तय करें)। पदानुक्रम प्रमेयों का प्रयोग किया जाता है यह प्रदर्शित करने के लिए कि समय और स्थान जटिलता वर्ग एक बनाते हैं पदानुक्रम जहां सख्त सीमाओं वाली कक्षाओं में कम भाषाएं होती हैं अधिक शिथिल सीमा वाले लोगों की तुलना में। यहां हम इसे परिभाषित और सिद्ध करते हैं अंतरिक्ष पदानुक्रम प्रमेय.

अंतरिक्ष पदानुक्रम प्रमेय अंतरिक्ष-निर्माण योग्य कार्यों की अवधारणा पर निर्भर करते हैं। नियतात्मक और गैर-नियतात्मक अंतरिक्ष पदानुक्रम प्रमेय बताते हैं कि सभी अंतरिक्ष-निर्माण योग्य कार्यों के लिए 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.