DSPACE

비슷한 이름의 DSpace에 관해서는 해당 문서를 참고하십시오.

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

복잡도 종류

DSPACE 측정은 특정 양의 메모리 공간을 사용하여 해결할 수 있는 모든 결정 문제의 집합인 복잡도 종류를 정의하는 데 사용된다. 각 함수 f(n)에 대해 SPACE(f(n))라는 복잡도 종류가 있으며, 이는 O(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))가 존재한다고 가정하자. M을 공간 s(n)에서 L을 결정하는 튜링 기계라고 하자. 가정에 의해 L ∉ DSPACE(O(1))이므로, 임의의 ${\displaystyle k\in \mathbb {N} }$에 대해 M의 입력 중 k보다 더 많은 공간을 요구하는 것이 존재한다.

k보다 더 많은 공간을 요구하는 가장 작은 크기(n으로 표시)의 입력 x를 잡고, ${\displaystyle {\mathcal {C}}}$를 입력 x에 대한 M의 모든 구성의 집합이라고 하자. M ∈ DSPACE(s(n))이므로, ${\displaystyle |{\mathcal {C}}|\leq 2^{c.s(n)}=o(\log n)}$이며, 여기서 c는 M에 의존하는 상수이다.

S를 x에 대한 M의 모든 가능한 교차열의 집합이라고 하자. x에 대한 M의 교차열 길이는 최대 ${\displaystyle |{\mathcal {C}}|}$임을 주목하자: 만약 이보다 길다면, 일부 구성이 반복되어 M은 무한 루프에 빠질 것이다. 교차열의 모든 요소에 대해 가능한 경우도 최대 ${\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)}$

비둘기집 원리에 따르면, ${\displaystyle {\mathcal {C}}_{i}(x)={\mathcal {C}}_{j}(x)}$인 i < j인 인덱스가 존재하며, 여기서 ${\displaystyle {\mathcal {C}}_{i}(x)}$와 ${\displaystyle {\mathcal {C}}_{j}(x)}$는 각각 경계 i와 j에서의 교차열이다.

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

위 정리는 공간 위계 정리에서 공간 구성 가능 함수 가정의 필요성을 시사한다.

• L = DSPACE(O(log n))
• PSPACE = ${\displaystyle \bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}(n^{k})}$
• EXPSPACE = ${\displaystyle \bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}(2^{n^{k}})}$

기계 모델

DSPACE는 전통적으로 결정론적 튜링 기계에서 측정된다. 몇 가지 중요한 공간 복잡도 종류는 준선형이다. 즉, 입력 크기보다 작다. 따라서 입력 크기 또는 출력 크기에 대해 알고리즘에 "비용을 부과"하는 것은 사용된 메모리 공간을 진정으로 포착하지 못할 것이다. 이는 입력 및 출력 테이프가 있는 다중 테이프 튜링 기계를 정의함으로써 해결되는데, 이는 표준 다중 테이프 튜링 기계와 동일하지만 입력 테이프에는 절대 쓰지 않고 출력 테이프에서는 절대 읽지 않는다는 점이 다르다. 이를 통해 L (로그 공간)과 같은 더 작은 공간 종류를 모든 작업 테이프(특수 입력 및 출력 테이프 제외)가 사용한 공간의 양으로 정의할 수 있다.

알파벳의 적절한 거듭제곱을 취하여 많은 기호를 하나로 묶을 수 있으므로, 모든 c ≥ 1 및 f(n) ≥ 1인 f에 대해 c f(n) 공간에서 인식 가능한 언어의 종류는 f(n) 공간에서 인식 가능한 언어의 종류와 동일하다. 이는 정의에서 점근 표기법의 사용을 정당화한다.

위계 정리

공간 위계 정리는 모든 공간 구성 가능 함수 ${\displaystyle f:\mathbb {N} \to \mathbb {N} }$에 대해 공간 ${\displaystyle O(f(n))}$에서 결정 가능하지만 공간 ${\displaystyle o(f(n))}$에서는 결정 불가능한 어떤 언어 L이 존재함을 보여준다.

 space hierarchy theorem 문서에 이 부분의 추가 정보가 있습니다.

다른 복잡도 종류와의 관계

DSPACE는 비결정론적 튜링 기계의 메모리 공간 종류인 NSPACE의 결정론적 대응물이다. 사비치 정리^[3]에 따르면, 다음과 같다.

${\displaystyle {\mathsf {DSPACE}}(s(n))\subseteq {\mathsf {NSPACE}}(s(n))\subseteq {\mathsf {DSPACE}}{\bigl (}(s(n))^{2}{\bigr )}.}$

NTIME은 다음과 같은 방식으로 DSPACE와 관련이 있다. 모든 시간 구성 가능 함수 t(n)에 대해,

${\displaystyle {\mathsf {NTIME}}(t(n))\subseteq {\mathsf {DSPACE}}(t(n))}$.

결정론적 시간에 대한 훨씬 더 나은 시뮬레이션이 알려져 있다: 만약 ${\displaystyle t(n)\geq n}$이라면,

${\displaystyle {\mathsf {DTIME}}(t(n))\subseteq {\mathsf {DSPACE}}\left({\sqrt {t(n)\log t(n)}}\right)}$

이는 윌리엄스의 결과^[4]로, 홉크로프트, 폴, 밸리언트의 이전 ${\displaystyle O(t/\log t)}$ 한계를 개선한 것이다.^[5]

반면에, ${\displaystyle s(n)\geq \log n}$인 모든 함수에 대해,

${\displaystyle {\mathsf {DSPACE}}(s(n))\subseteq {\mathsf {DTIME}}{\bigl (}2^{O(s(n))}{\bigr )}}$.