사비치의 정리

계산 복잡성 이론에서, 1970년 월터 사비치(Walter Savitch)에 의해 증명된 사비치(Savitch)의 정리는 결정론적 공간 복잡성과 비결정론적 공간 복잡성 사이의 관계를 제공한다.\$Oomega(\log(n$\log(n$)}$ 함수 f${\displaystyle \mathrm{\Omega }}$(${\displaystyle \log }$(n)})에 대해$,$

${\displaystyle {\mathsf {NSPACE}\좌측(f\좌측(n\우측)\우측)\subseteq {\mathsf {DSPACE}\좌측(n\우측)^{2}\우측)}$

즉, 비결정론적 튜링 시스템이 $f{\displaystyle }$($){\displaystyle f(n)}$ 공간을$$ 사용하여 문제를 해결할 수 있는 경우, 결정론적 튜링 시스템은 해당 공간 바인딩의 사각형에서 동일한 문제를 해결할 수 있다.^[1]비록 비결정론이 시간에 기하급수적인 이득을 가져올 수 있는 것처럼 보이지만, 이 정리는 그것이 공간 요건에 현저하게 더 제한적인 영향을 미친다는 것을 보여준다.^[2]

증명

증명서는 지시된 그래프에서 두 정점 사이에 경로가 있는지 여부를 결정하는 문제인 STCON 알고리즘에 의존한다. 이 두$$ $정점$은$$N {\$displaystyle$n} $정점$에${\displaystyle }$대해${\displaystyle }$O ( ( ( ${\displaystyle \mathrm{로그}}$ ${\displaystyle {}^{}}$ ) ${\displaystyle {2\mathrm{}}^{}}$) ${\$ n$)^{2}\rig)}}$ 공간으로$$ 실행된다.알고리즘의 기본 개념은 다소 일반적인 문제를 재귀적으로 해결하는 것으로, 대부분의 k 에지에서 사용하는 정점 s에서 다른 정점 t까지의 경로의 존재를 시험하는 것이다. 여기서 k는 재귀 알고리즘에 입력으로 주어지는 매개변수다.STCON은 k를 n으로 설정하여 이 문제를 해결할 수 있다.s에서 t까지의 k-edge 경로에 대해 시험하기 위해 s에서 u, u에서 t까지의 길이의 절반의 경로를 재귀적으로 검색하여 각 꼭지점 u가 s-t 경로의 중간점이 될 수 있는지 여부를 시험할 수 있다.Python 구문(Python 구문)에서 유사코드를 사용하여 이 알고리즘을 다음과 같이 표현할 수 있다.

반항하다 k_edge_path(s, t, k) -> 바가지 긁다:     """k는 처음에는 n(정점 수)과 같다""""     만일 k == 0:         돌아오다 s == t     만일 k == 1:         돌아오다 (s, t) 에 가장자리     을 위해 u 에 정점:         만일 k_edge_path(s, u, 마루를 깔다(k / 2)) 그리고 k_edge_path(u, t, 천장을 치다(k / 2)):             돌아오다 진실의     돌아오다 거짓의 

This search calls itself to a recursion depth of ${\displaystyle O(\log n)}$ levels, each of which requires ${\displaystyle O(\log n)}$ bits to store the function arguments and local variables at that level: k and all vertices (s, t, u) require ${\displaystyle O(\log n)}$ bits each.따라서 $총{\displaystyle }$ 보조 공간 복잡성은 O${\displaystyle }$(${\displaystyle }$( ${\displaystyle \log }$ ${\displaystyle {}^{}n}$ )${\displaystyle {}^{}{2\mathrm{}}^{}}$ )$${\$displaystyle$O\$left ((\log$ n$)^{2}\right)}$이다$.$^{[Note 1]} 위에서 고수준 언어로 프로그램 형태로 설명하였지만 튜링 시스템에 동일한 점증적 공간을 바인딩하여 동일한 알고리즘을 구현할 수 있다.

이 알고리즘이 정리를 암시하는 이유를 보려면 다음을 고려하십시오.For any language ${\displaystyle L\in {\mathsf {NSPACE}}(f(n))}$, there is a Turing machine ${\displaystyle M}$ which decides ${\displaystyle L}$ in space ${\displaystyle f(n)}$. Assume w.l.o.g. the alphabet is a binary alphabet ${\displaystyle \{0,1\}}$ (viz.${\displaystyle L\subseteq \{0}$, ${\displaystyle 1{}^{\ast }}$ ∗ ${\$입력 단어 x${\displaystyle }x{\displaystyle \{0}$$,$${\displaystyle 1}$ ${\displaystyle {\ast \}}^{}}$ ${\$에 대해$,$ 입력 $x$에서 실행할 때$$ 정점이 $M{\displaystyle }$ ${\displaystyle$ $M$$}$의 구성인 방향$$ 그래프 G ${\displaystyle x_{}^{}}$ ${\displaystyle {}_{}^{}}$ ${\$$displaystyle$ $G_{x}^{M$$}$이 있다$.$그러한 구성은 무한히 많을 수 있다. 예를 들어, $M{\displaystyle }$ ${\displaystyle M}$이(가) 테이프에 기호를 계속$$ 쓰고 머리를 오른쪽으로 움직이는 경우, ad infinitum.그런 다음 구성이 임의로 커진다.그러나, $우리$는 x${\displaystyle l}$ L$[\$$displaystyle$ x$\\$$in$ L$}$의 여부를 결정하려면 $최대{\displaystyle }$$f{\displaystyle }$($n$$$)$${\$displaystyle$ $x$$\\in$ L$}$의 공간이$$ 필요하다는 것을 알고 있으므로, 그러한 구성은 허용된다$.$There are finitely many admissible configurations; namely ${\displaystyle 2^{O\left(f(n)\right)}}$. Therefore, the induced subgraph ${\displaystyle [G_{x}^{M}]}$ of ${\displaystyle G_{x}^{M}}$ containing (exactly) the admissible configurations has ${\displaystyle 2^{O\left(f(n)\right)}}$${\displaystyle 2^{O\left(f(n)\$오른쪽$)}}$정점$$.For each input ${\displaystyle x\in \{0,1\}^{n}}$, ${\displaystyle [G_{x}^{M}]}$ has a path from the starting configuration to an accepting configuration if and only if ${\displaystyle x\in L}$. Thus by deciding connectivity in ${\displaystyle [G_{x}^{M}]}$, we can decide membership of ${\displaystyle x}$ in ${\displaystyle L}$. By the above algorithm this can be done deterministically in space ${\displaystyle O\left(\left(\log 2^{O\left(f(n)\right)}\right)^{2}\right)=$$O\left(f\left(n\right)^{2}\right$ 따라서 $L{\displaystyle }$ ${\displaystyle L}$은$($는) $D{\displaystyle \mathsf{}}$ S ${\displaystyle \mathsf{P}}$ A ${\displaystyle \mathsf{C}}$ E${\displaystyle }$(${\displaystyle f{}^{}}$(${\displaystyle n^{}}$ ${\displaystyle {)}^{}}$ ${\displaystyle {}^{}}$) ${\$2}\}에 있다$.$

Since this holds for all ${\displaystyle f\in \Omega (\log n)}$ and all ${\displaystyle L\in {\mathsf {NSPACE}}\left(f\left(n\right)\right)}$, we get the statement of the theorem:

For all functions ${\displaystyle f\in \Omega (\log n)}$, ${\displaystyle {\mathsf {NSPACE}}\left(f\left(n\right)\right)\subseteq {\mathsf {DSPACE}}\left(f\left(n\right)^{2}\right)}$.

코롤러리

정리의 일부 중요한 윤곽은 다음과 같다.

• PSpace = NPSPACE
  • 이것은 다항함수의 제곱이 여전히 다항함수라는 사실에서 직접적으로 나타난다.다항 시간 복잡성 등급인 P와 NP 사이에는 유사한 관계가 존재하지 않는다고 생각되지만, 이는 여전히 공개적인 질문이다.
• NL ⊆ L²
  • STCON은 NL 완성형이며, 따라서 NL의 모든 언어도 복잡도 등급 ${\displaystyle L^{\mathrm{}}}$ 2${\displaystyle {}^{}}$= D ${\displaystyle S\mathsf{}}$ ${\displaystyle \mathsf{P}}$ ${\displaystyle \mathsf{A}}$ ${\displaystyle \mathsf{C}}$ ${\displaystyle \mathsf{E}}$(${\displaystyle {}^{}}$( ${\displaystyle {\log }^{}}$ ${\displaystyle n^{}}$) ${\displaystyle {}^{}}$) ${\$에 있다.$L}^{2}={\mathsf$ {$DSPACE}\왼쪽(\log$ n$\오른쪽)^{2}\오른쪽$ .

참고 항목

• 지수 시간 가설
• 임메르만-셀레프세니 정리

메모들

참조

• Arora, Sanjeev; Barak, Boaz (2009), Computational complexity. A modern approach, Cambridge University Press, ISBN 978-0-521-42426-4, Zbl 1193.68112
• Papadimitriou, Christos (1993), "Section 7.3: The Reachability Method", Computational Complexity (1st ed.), Addison Wesley, pp. 149–150, ISBN 0-201-53082-1
• Savitch, Walter J. (1970), "Relationships between nondeterministic and deterministic tape complexities", Journal of Computer and System Sciences, 4 (2): 177–192, doi:10.1016/S0022-0000(70)80006-X, hdl:10338.dmlcz/120475
• Sipser, Michael (1997), "Section 8.1: Savitch's Theorem", Introduction to the Theory of Computation, PWS Publishing, pp. 279–281, ISBN 0-534-94728-X

외부 링크

• 랜스 포트나우, 복잡성의 기초, 제 18장: 사비치의 정리.09/09/09 액세스.
• 리처드 J. 립튼, 새비치의 정리.증거가 어떻게 발견되었는지에 대한 역사적 설명을 제공한다.