공간 위계 정리

이 기사는 위키피디아의 품질 기준을 충족시키기 위해 정리가 필요할 수 있다.구체적인 문제는 백과사전의 글이 아닌 강의로 1인칭으로 쓰여 있다는 점이다. 가능한 경우 이 문서를 개선하는 데 도움을 주십시오. (2019년 12월) (이 템플리트 메시지를 제거하는 방법과 시기 알아보기)

계산 복잡성 이론에서 공간 계층 구조 이론은 결정론적 기계와 비결정론적 기계 모두가 특정 조건에 따라 더 많은 공간(비절제적으로)에서 더 많은 문제를 해결할 수 있다는 것을 보여주는 분리 결과들이다.예를 들어 결정론적 튜링 기계는 공간 n보다 공간 n 로그 n에서 더 많은 의사결정 문제를 해결할 수 있다.시간에 대한 다소 약한 유사 이론은 시간 계층 구조 이론이다.

계층구성의 기초는 더 많은 시간 또는 더 많은 공간과 함께 더 많은 기능을 계산하는 능력(또는 더 많은 언어를 결정하는 능력)이 온다는 직관에 있다.계층 구조 이론은 시간과 공간의 복잡성 클래스가 보다 완화된 범위를 가진 클래스보다 더 적은 언어를 포함하는 계층을 형성한다는 것을 증명하기 위해 사용된다.여기서 우리는 우주 계층의 정리를 정의하고 증명한다.

공간 계층 구조 이론은 공간 구성 가능한 기능의 개념에 의존한다.결정론적 및 비결정론적 공간 계층 구조 이론에 따르면 모든 공간 구성 가능 함수에 대해 f(n)

${\displaystyle \mathsf{S}}$ ${\displaystyle \mathsf{P}}$ ${\displaystyle \mathsf{A}}$ ${\displaystyle \mathsf{C}}$ E${\displaystyle }$(${\displaystyle o}$ ( ${\displaystyle f}$ ${\displaystyle (n}$)${\displaystyle }$) )${\displaystyle ⊊}$ S ${\displaystyle P\mathsf{}}$ ${\displaystyle \mathsf{A}}$ C ${\displaystyle \mathsf{E}}$(${\displaystyle f}$ )${\displaystyle \{}$ S P A C ${\displaystyle \mathsf{E}}$ (${\displaystyle f}$ ) ${\displaystyle {\mathsf {SPACE}\좌측(o(f)(n)\오른쪽)\subsetneq {\mathsp$ {$Space$

여기서 SPACE는 DSPACE 또는 NSPACE를 의미하며 o는 little o 표기법을 가리킨다.

성명서

Formally, a function ${\displaystyle f:\mathbb {N} \longrightarrow \mathbb {N} }$ is space-constructible if ${\displaystyle f(n)\geq \log ~n}$ and there exists a Turing machine which computes the function ${\displaystyle f(n)}$ in space ${\displaystyle O(f(n))}$ when st입력 ${\displaystyle {1n}^{}}$ ${\$을(를) 사용한 아칭$,$ 여기서 ${\displaystyle {1n}^{}}$ ${\$은 n 연속 1초의 문자열을 나타낸다$$.우리가 함께 작업하는 대부분의 공통 함수는 다항식, 지수, 로그 등 공간구성이 가능하다.

For every space-constructible function ${\displaystyle f:\mathbb {N} \longrightarrow \mathbb {N} }$, there exists a language L that is decidable in space ${\displaystyle O(f(n))}$ but not in space ${\displaystyle o(f(n))}$.

증명

여기서 목표는 $공간{\displaystyle }$ O${\displaystyle }$( ${\displaystyle f}$ (${\displaystyle }$) ${\displaystyle$ O$(f(n)}$에서 결정할 수 있는 언어를 정의하는 ${\displaystyle 것}$이지만 $공간{\displaystyle }$O${\displaystyle }$(${\displaystyle n}$)$${\$displaystyle o(f(n)}$에서는 결정되지 않는다. 여기서 언어 L$:$

${\displaystyle L=\{~(\langle M\angle ,10^{k}):M{\mbox{{pace }}}\leq f(\langle M\rangle, 10^{k}){\\mbox{{}}{\langle M\rangle, 10^{k}}\}}}}}}}}}}}}}{\mbox{{{}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$

Now, for any machine M that decides a language in space ${\displaystyle o(f(n))}$, L will differ in at least one spot from the language of M. Namely, for some large enough k, M will use space ${\displaystyle \leq f( \langle M\rangle ,10^{k} )}$ on ${\displaystyle ($$\langle M\rangele ,10^{k}}$ 따라서$$ 값이 다를 것이다.

반면 L은 S $P{\displaystyle \mathsf{}}$ ${\displaystyle \mathsf{A}}$ ${\displaystyle \mathsf{C}}$ ${\displaystyle \mathsf{E}}$( ${\displaystyle f}$($){\displaystyle {\mathsf {SPACE}(f(n)})}$에 있다$.$L언어를 결정하는 알고리즘은 다음과 같다.

1. 입력 ${\displaystyle x}$에서 공간 구성성을 사용하여$$ $f{\displaystyle }$( x${\displaystyle }$) ${\displaystyle f($ x $)}$을(를) 계산하고 테이프의 $f{\displaystyle }$( x${\displaystyle }$) ${\displaystyle f($ x $)}$ 셀을$$ 표시하십시오.$f{\displaystyle }$( ${\displaystyle x}$) ${\displaystyle f($x$)}$개$$ 이상의 셀을 사용하려고 시도할 때마다 거부하십시오.
2. x가 ${\displaystyle \mathrm{일부}}$ TM M에 대해$$${\displaystyle k^{}}$ M$display$ , 10 k {\displaystyle $\langle M\$angle ,$10^{k}}$ 형식이 아닌 경우 거부한다.
3. 입력 x에서 최대 $($ ${\displaystyle x^{}}$) {\$displaystyle$ 2$^{f($ x )}}단계$$($f{\displaystyle }$($){\displaystyle f(x )}$ 공간$$ 사용)에 대해 M을 시뮬레이션하십시오.시뮬레이션에서 $f{\displaystyle }$( ${\displaystyle x}$) ${\displaystyle f($ x $)}$개 이상의 공간$$ 또는 ${\displaystyle {2f}^{}}$( ${\displaystyle x^{}}$) ${\$ x $)}}$개 이상의 연산을$$ 사용하려고 하면 거부한다.
4. 이 시뮬레이션 중에 M이 x를 수락하면 거절하고, 그렇지 않으면 수락한다.

3단계 참고: 입력 x에서 M이 정지하지 않는 경우를 피하기 위해 실행은 2 ${\displaystyle f^{}}$( $){\$ x $)}}$ 단계로$$ 제한된다.즉, M이 $필요$에 따라$$ O${\displaystyle }$( ${\displaystyle f}$( x${\displaystyle }$)${\displaystyle O(f(x))}$의 공간만 사용하지만 무한정 실행되는 경우.

위의 증명은 PSPACE의 경우에 부합하는 반면 NPSPACE의 경우에 우리는 약간의 변화를 주어야 한다.중요한 점은 결정론적 TM에서는 수용과 거부를 쉽게 역전시킬 수 있지만(4단계 기준) 비결정론적 기계에서는 이것이 불가능하다는 것이다.

NPSPACE의 경우 먼저 L:를 재정의한다.

${\displaystyle L=\{~(\langle M\angle ,10^{k}):M{\mbox{{pace }}}\leq f(\langle M\rangle, 10^{k}){\\mbox{{}}}{\mbox{{}}}}}}}}}}}(\langle M\rangle, 10^{k}~}\}}}}}})를 수락함$

이제 4단계를 다음과 같이 수정하여 L을 받아들이도록 알고리즘을 변경해야 한다.

• 이 시뮬레이션 중에 M이 x를 수락한 경우 수락하거나, 그렇지 않은 경우 거절하십시오.

우리는 이제 $o{\displaystyle }$(${\displaystyle f}$ ( $){\displaystyle o ($f$(n)}$ 셀을$$ 사용하여 TM이 L을 결정할 수 없다는 것을 모순으로 증명할 것이다.Assuming L can be decided by some TM M using ${\displaystyle o(f(n))}$ cells, and following from the Immerman–Szelepcsényi theorem, ${\displaystyle {\overline {L}}}$ can also be determined by a TM (which we will call ${\displaystyle {\overline {M}}}$) using ${\displaystyle o(f(n))}$$$ 세포들여기 모순이 있다. 그러므로 우리의 가정은 거짓이어야 한다.

1. If ${\displaystyle w=(\langle {\overline {M}}\rangle ,10^{k})}$ (for some large enough k) is not in ${\displaystyle {\overline {L}}}$ then M will accept it, therefore ${\displaystyle {\overline {M}}}$ rejects w, therefore w is in ${\displaystyle {\overline {L}}}$ (contra어법상의
2. If ${\displaystyle w=(\langle {\overline {M}}\rangle ,10^{k})}$ (for some large enough k) is in ${\displaystyle {\overline {L}}}$ then M will reject it, therefore ${\displaystyle {\overline {M}}}$ accepts w, therefore w is not in ${\displaystyle {\overline {L}}}$ (contra어법상의

비교 및 개선

공간 계층 구조 정리는 다음과 같은 여러 가지 면에서 유사 시간 계층 구조 정리보다 강하다.

• 그것은 s(n)가 적어도 n이 아닌 log n이 되어야 한다.
• 그것은 어떤 점증적 차이로도 클래스를 분리할 수 있는 반면, 시간 계층 구조 정리는 로그 인수에 의해 분리될 것을 요구한다.
• 그것은 단지 그 기능이 시간구성이 아니라 공간구성이 될 것을 요구한다.

시간보다는 우주에서 수업을 분리하는 것이 더 쉬워진 것 같다.실제로 시간 계층 구조 정리는 그 시작 이후 현저한 향상을 거의 보지 못한 반면, 비결정론적 공간 계층 구조 정리는 빌리암 게퍼트가 2003년 논문 "공간 계층 구조 수정"에서 적어도 한 가지 중요한 개선을 보았다.본 논문은 그 정리를 다음과 같이 몇 가지 일반화하였다.

• 그것은 공간 구성 요건을 완화한다.Instead of merely separating the union classes ${\displaystyle {\mathsf {DSPACE}}(O(s(n))}$ and ${\displaystyle {\mathsf {DSPACE}}(o(s(n))}$, it separates ${\displaystyle {\mathsf {DSPACE}}(f(n))}$ from ${\$$displaystyle {\mathsf {DSPACE}(g$)($n{\displaystyle }$)} 여기서$$ f$)($n${\displaystyle )}$는 $임의$의 O${\displaystyle (}$ ${\displaystyle s}$) ${\displaystyle O(s)(n)}$ 함수이고$$$$ g(n)는 계산 가능한 $o{\displaystyle (s}$ ${\displaystyle )}$ ${\displaysty o(n)$ 함수다$$.이 기능들은 공간구축이 가능하거나 심지어 단조로운 증가가 필요하지 않다.
• 그것은 하나의 클래스에 있지만 다른 클래스는 아닌 단일 언어 또는 집계 언어를 식별한다.원래의 정리에서는 분리된 언어가 제멋대로였다.
• ${\displaystyle s}$( n${\displaystyle }$) ${\displaystyle s(n)}$이(가) 최소한 로그 n이 될 필요는$$ 없으며, 비결정적으로 완전히 공간 구성 가능한 기능이 될 수 있다.

공간 계층 구조 개선

If space is measured as the number of cells used regardless of alphabet size, then ${\displaystyle {\mathsf {SPACE}}(f(n))={\mathsf {SPACE}}(O(f(n)))}$ because one can achieve any linear compression by switching to a larger alphabet.그러나 공간을 비트 단위로 측정함으로써 결정론적 공간에 대해 훨씬 더 날카로운 분리를 달성할 수 있다.최대 승수 상수까지 정의되는 대신에, 공간은 이제 부가 상수까지 정의된다.However, because any constant amount of external space can be saved by storing the contents into the internal state, we still have ${\displaystyle {\mathsf {SPACE}}(f(n))={\mathsf {SPACE}}(f(n)+O(1))}$.

f는 공간구성이 가능하다고 가정해 보자.SPACE는 결정론적이다.

• 튜링 기계를 포함한 다양한 순차 연산 모델의 경우 SPACE(f(n)-Ω(log(f(n)+n))) ⊊ SPACE(f(n))This holds even if SPACE(f(n)-ω(log(f(n)+n))) is defined using a different computational model than ${\displaystyle {\mathsf {SPACE}}(f(n))}$ because the different models can simulate each other with ${\displaystyle O(\log(f(n)+n))}$ space overhead.
• 특정 계산 모델의 경우 SPACE(f(n)-Ω(1) ⊊ SPACE(f(n))까지 가지고 있다.특히, 이것은 우리가 알파벳, 입력 테이프의 헤드의 수, 워크테이프의 헤드의 수(단일 워크테이프를 사용함)를 수정하고, 워크테이프의 방문한 부분에 구분자를 추가하면 튜링 기계에 적용된다(공간 사용량을 늘리지 않고도 확인할 수 있음).SPACE(f(n))는 작업 테이프가 무한인지 반무한지에 따라 달라지지 않는다.또한 f(n)가 테이프당 공간 사용을 제공하는 SPACE 구성 가능한 튜플이거나 SPACE(f)(n)-Ω(log(f(n)))- 총 공간 사용량을 제공하는 구성 가능한 숫자일 경우(각 테이프의 길이를 저장하기 위한 오버헤드를 계산하지 않음) 작업 테이프의 수를 고정할 수 있다.

그 증명은 공간 위계질서의 정리의 증명과 유사하지만, 다음과 같은 두 가지 복잡성을 가지고 있다.범용 튜링 기계는 공간 효율적이어야 하고, 반대로 되돌리는 것은 공간 효율적이어야 한다.일반적으로 범용 튜링 시스템을 $O{\displaystyle (\log }$ ${\displaystyle }$ ${\displaystyle (s}$ p ${\displaystyle a}$ e${\displaystyle ))}$ ${\displaystyle$ O$(\log(space))}$ 공간$$ 오버헤드로 구성할 수 있으며, 적절한 $가정$에서는 O${\displaystyle }$(${\displaystyle 1}$ )$${\$displaystyle O$(1$)}$ 공간$$ 오버헤드(시뮬레이션되는 시스템에 따라 다를 수 있음)만 구성할 수 있다.반전의 경우, 시뮬레이션 기계가 무한(공간 구속) 루프를 입력하여 거부하는지 여부를 어떻게 검출하는지가 핵심 쟁점이다.단순히 스텝 수를 세는 것만으로도 공간 소비량이 약 $f{\displaystyle }$($){\displaystyle f(n)}$ 증가하게 된다$.$ 잠재적으로 기하급수적인 시간 증가의 비용으로 다음과 같이 루프를 공간 효율적으로 검출할 수 있다.^[1]

기계를 수정하여 모든 것을 지우고 성공 시 특정 구성 A로 이동하십시오.깊이 우선 검색을 사용하여 시작 구성에서 바인딩된 공간에서 A에 연결할 수 있는지 확인하십시오.검색은 A에서 시작하여 A로 연결되는 구성을 검토한다.결정론 때문에, 이것은 루프에 들어가지 않고 제자리에 있을 수 있다.

또한, 공간을 초과하는 것에 대한 모든 구성을 반복하고 (깊이 우선 검색을 사용하여) 초기 구성이 그 중 하나로 이어지는지 여부를 점검함으로써 기계가 (공간 범위 내에서 루핑하는 것이 아니라) 공간을 초과하는지를 확인할 수 있다.

코롤러리

코롤러리 1

For any two functions ${\displaystyle f_{1}}$, ${\displaystyle f_{2}:\mathbb {N} \longrightarrow \mathbb {N} }$, where ${\displaystyle f_{1}(n)}$ is ${\displaystyle o(f_{2}(n))}$ and ${\displaystyle f_{2}}$ is space-constructible, ${\displaystyle \mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}(}$${\displaystyle f_{}}$ ${\displaystyle {1\mathrm{}}_{}}$( ${\displaystyle n}$)${\displaystyle ⊊}$ S ${\displaystyle P\mathsf{}}$ ${\displaystyle \mathsf{A}}$ ${\displaystyle \mathsf{C}}$ ${\displaystyle \mathsf{E}}$( ${\displaystyle f}$ ${\displaystyle {}_{}}$(${\displaystyle }$n )${\displaystyle }$) ${\displaystyle {\mathsf {Space}(f_{1}(n))\subsetneq$ {\$mathsf$ {$Space}(f_{2$}($n$ .

이 장막은 우리에게 다양한 공간 복잡성 계층을 구분하도록 해준다.$n{\displaystyle {}^{}}$ ${\displaystyle k^{}}$ ${\$ 기능에 대해 자연수 k에 대해 공간구성이 가능하다$$.Therefore for any two natural numbers ${\displaystyle k_{1}<k_{2}}$ we can prove ${\displaystyle {\mathsf {SPACE}}(n^{k_{1}})\subsetneq {\mathsf {SPACE}}(n^{k_{2}})}$. We can extend this idea for real numbers in the following corollary.이것은 PSPACE 클래스 내의 상세한 계층 구조를 보여준다.

코롤러리 2

For any two nonnegative real numbers ${\displaystyle a_{1}<a_{2},{\mathsf {SPACE}}(n^{a_{1}})\subsetneq {\mathsf {SPACE}}(n^{a_{2}})}$.

코롤러리 3

NL ⊊ PSPACE.

증명

Savitch's theorem shows that ${\displaystyle {\mathsf {NL}}\subseteq {\mathsf {SPACE}}(\log ^{2}n)}$, while the space hierarchy theorem shows that ${\displaystyle {\mathsf {SPACE}}(\log ^{2}n)\subsetneq {\mathsf {SPACE}}(n)}$.따라서 우리는 TQBF가 PSpace-완전하므로 TQBF n NL과 함께 이러한 관점을 얻는다.

이것은 또한 NL ⊊ NPSPACE를 보여주기 위한 비결정적 공간 계층 구조 정리와 PSPACE = NPSPACE를 보여주기 위해 Savitch의 정리를 사용하여 증명될 수 있었다.

코롤라리 4호

PSpace ⊊ EXPSPACE.

이 마지막 관점은 다루기 어려운 결정 가능한 문제의 존재를 보여준다.즉, 그들의 의사결정 절차는 다항식 공간 이상을 사용해야 한다.

코롤러리 5

PSPACE에는 임의로 큰 지수를 요구하는 문제가 있다. 따라서 PSPACE는 일정한 k에 대해 DSPACE(n^k)로 붕괴되지 않는다.

참고 항목

• 시간 계층 정리

참조

• Arora, Sanjeev; Barak, Boaz (2009). Computational complexity. A modern approach. Cambridge University Press. ISBN 978-0-521-42426-4. Zbl 1193.68112.
• 루카 트레비산계층 구성 참고 사항.유인물 7. CS172: 오토마타, 계산성 및 복잡성U.C. 버클리2004년 4월 26일.
• 빌리암 게퍼트공간 계층 구조 정리가 수정되었다.이론 컴퓨터 과학, 제295권, 번호 1-3, 페이지 171-187.2003년 2월 24일.
• Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. 제9.1절 306~310쪽: 계층 구조 정리.
• Papadimitriou, Christos (1993). Computational Complexity (1st ed.). Addison Wesley. ISBN 0-201-53082-1. 제7.2절: 위계 정리, 페이지 143–146.