디스페이스

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "DSPACE" – 뉴스 · 신문 · 책 · 학자 · JSTOR(2009년 10월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

계산 복잡성 이론에서, DSPACE 또는 SPACE는 결정론적 튜링 기계의 메모리 공간의 자원을 설명하는 계산적 자원이다.이는 "정상적인" 물리적 컴퓨터가 주어진 연산 문제를 주어진 알고리즘으로 해결하는 데 필요한 총 메모리 공간을 나타낸다.

복잡도 클래스

DSPACE 측정은 특정 메모리 공간을 사용하여 해결할 수 있는 모든 의사결정 문제의 집합인 복잡성 클래스를 정의하기 위해 사용된다.각 기능 f(n)에 대해 공간 O(f(n)를 이용한 결정론적 튜링 기계에 의해 해결될 수 있는 일련의 의사결정 문제인 복잡도 등급 SPACE(f(n)가 있다.다른 복잡성 측정(교대 등)에는 제한이 있을 수 있지만, 사용할 수 있는 계산 시간의 양에는 제한이 없다.

몇 가지 중요한 복잡성 등급은 DSPACE 관점에서 정의된다.여기에는 다음이 포함된다.

• REG = DSPACE(O(1)), 여기서 REG는 정규 언어의 클래스다.실제로, REG = DSPACE(o(log log n) (즉, Ω(log log n) 공간은 모든 비정규 언어를 인식하기 위해 필요하다.^[1][2]

증명: s(n) = o(log log n)에 대한 비정규 언어 L ∈ DSPACE(s(n)가 존재한다고 가정합시다.공간 s(n)에서 L을 결정하는 튜링 기계가 M을 두자.우리의 가정 L ∉ DSPACE(O(1)). 따라서 임의의 k ${\displaystyle k\mathbb{}}$ N${\$에 대해 k보다$$더 많은 공간을 요구하는 M의 입력이 존재한다.

Let x be an input of smallest size, denoted by n, that requires more space than k, and ${\displaystyle {\mathcal {C}}}$ be the set of all configurations of M on input x. Because M ∈ DSPACE(s(n)), then ${\displaystyle {\mathcal {C}} \leq 2^{c.s(n)}=o(\log n)}$, where c is a constanM에 의존한다.

S는 x에 M의 가능한 모든 교차 시퀀스의 집합을 나타냅시다. x에 있는 M의 교차 시퀀스의 길이는 ${\displaystyle 최대\mathcal{}}$ C $displaystyle${\$mathcal{C}}$: 그것보다 길면 어떤 구성이 반복되며, M은 무한 루프에 들어간다.또한 교차 시퀀스의 모든 요소에 대해 ${\displaystyle 최대\mathcal{}}$ C $displaystyle {\mathcal {C}$개의 가능성이$$ 있으므로, X에 있는 M의 서로 다른 교차 시퀀스의 수는 다음과 같다.

${\displaystyle S \leq {\mathcal {C}} ^{ {\mathcal {C}} }\leq (2^{c.s(n)})^{2^{c.s(n)}}=2^{c.s(n).2^{c.s(n)}}<2^{2^{2c.s(n)}}=2^{2^{o(\log \log n)}}=o(n)}$

pigeonhole 원칙에 따르면, 나는 < 지수, b에서 j 그런 C가 나는())를 Cj({\displaystyle{{C\mathcal}}_ᆱ())={{C\mathcal}}_ᆳ())}, C나는()){\displaystyle{{C\mathcal}}_ᆵ())}, Cj({\displaystyle{{C\mathcal}}_ᆷ())}은 그 도하를 존재하oundary i와 j, 각각

x는 i + 1에서 j까지 모든 셀을 제거하여 x에서 얻은 문자열로 하자.기계 M은 여전히 입력 x'에서 입력 x'와 정확히 같은 방식으로 동작하므로 x'를 계산하는 것과 동일한 공간이 필요하다.그러나, x' < x , x의 정의와 모순된다.따라서 가정된 언어 L은 존재하지 않는다.□

위와 같은 정리는 공간 위계 정리에서 공간 구성 함수 가정이 필요하다는 것을 내포하고 있다.

• L = DSPACE(O(log n))
• PSPACE = $\bigcup {\displaystyle \underset{}{}}$ ${\displaystyle \underset{}{k}}$ ${\displaystyle \underset{}{\in }}$ ${\displaystyle \underset{}{N\mathbb{}}}$ D ${\displaystyle \underset{}{S}\mathsf{}}$ ${\displaystyle \mathsf{P}}$ A ${\displaystyle \mathsf{C}}$ ${\displaystyle \mathsf{E}}$(${\displaystyle n^{}}$ k${\displaystyle {}^{}}$) ${\displaystyle \bigcup _{k\in \mathb{N}}{\mathsf {DSpace}}{d^{k}}}}}$
• EXPSPACE = $\bigcup {\displaystyle \underset{}{}}$ ${\displaystyle \underset{}{k}}$ ${\displaystyle \underset{}{\in }}$ ${\displaystyle \underset{}{N\mathbb{}}}$ D ${\displaystyle \underset{}{S}\mathsf{}}$ ${\displaystyle \mathsf{P}}$ ${\displaystyle \mathsf{A}}$ ${\displaystyle \mathsf{C}}$ ${\displaystyle \mathsf{E}({{2n}^{}}^{}}$) ${\displaystyle \bigcup _{k\in \mathb{N}{\mathsf{DSpace}}(2^{n^{k})}}}}$

기계 모델

DSPACE는 전통적으로 결정론적 튜링 기계로 측정된다.몇 가지 중요한 공간 복잡성 등급은 입력 크기보다 작은 하위 선형이다.따라서 입력 크기 또는 출력의 크기에 대한 알고리즘을 "충전"하면 실제로 사용된 메모리 공간을 포착하지 못할 것이다.이 문제는 입력 테이프가 절대 쓰이지 않을 수 있고 출력 테이프가 절대 읽히지 않을 수 있다는 점을 제외하면 표준 멀티 테이프 튜링 기계인 입출력기를 정의함으로써 해결된다.이를 통해 L(로그 공간)과 같은 작은 공간 클래스를 모든 작업 테이프(특수 입력 및 출력 테이프 제외)가 사용하는 공간의 양 측면에서 정의할 수 있다.

많은 기호가 알파벳의 적절한 힘을 얻어 하나로 채워질 수 있기 때문에, f(n) ≥ 1과 f의 모든 c n 1에 대해, c(n) 공간에서 인식 가능한 언어의 클래스는 f(n) 공간에서 인식 가능한 언어의 클래스와 동일하다.이것은 정의에서 빅 O 표기법을 사용하는 것을 정당화한다.

위계 정리

The space hierarchy theorem shows that, for every space-constructible function ${\displaystyle f:\mathbb {N} \to \mathbb {N} }$, there exists some language L which is decidable in space ${\displaystyle O(f(n))}$ but not in space ${\displaystyle o(f(n))}$.

기타 복잡도 클래스와의 관계

DSPACE는 NSPACE의 결정론적 상대물로서 비결정론적 튜링 기계의 메모리 공간 등급이다.사비치의 정리대로라면,^[3] 우리는 그것을 가지고 있다.

${\displaystyle {\mathsf {DSPACE}[s(n)]\subseteq {\mathsf {NSPACE}\subseteq {\dSpace}[s(n)^{2}].}$

NTIME은 다음과 같은 방식으로 DSPACE와 관련이 있다.어떤 시간 구성 가능한 함수 t(n)는 다음과 같다.

${\displaystyle \mathsf{N}}$ ${\displaystyle \mathsf{T}}$ ${\displaystyle \mathsf{I}}$ ${\displaystyle \mathsf{M}}$ E${\displaystyle }$( t${\displaystyle }$( ${\displaystyle n}$)${\displaystyle }$) ${\displaystyle \subseteq }$ D ${\displaystyle \mathsf{S}}$ P ${\displaystyle \mathsf{A}}$ ${\displaystyle \mathsf{C}}$ ${\displaystyle E}$( t${\displaystyle }$) ${\displaystyle \{}$ ${\displaystyle {\mathsf {NTIME}(t(n)}\subseteq {\mathsf {dSpace}(t)(n$

참조

• Szepietowski, Andrzej (1994). Turing Machines with Sublogarithmic Space. Springer Science+Business Media. ISBN 978-3-540-58355-4.
• Arora, Sanjeev; Barak, Boaz (2009). Computational complexity. A modern approach. Cambridge University Press. ISBN 978-0-521-42426-4. Zbl 1193.68112.

외부 링크

• 복잡성 동물원: DSPACE(f(n)).