DSPACE

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

복잡도 종류

DSPACE 측정은 특정 양의 메모리 공간을 사용하여 해결할 수 있는 모든 결정 문제의 집합인 복잡도 종류를 정의하는 데 사용된다. 각 함수 f(n)에 대해 SPACE(f(n))라는 복잡도 종류가 있으며, 이는 O(f(n)) 공간을 사용하는 결정론적 튜링 기계에 의해 해결될 수 있는 결정 문제의 집합이다. 사용될 수 있는 계산 시간의 양에는 제한이 없지만, 다른 복잡도 측정(예: 교대)에는 제한이 있을 수 있다.

몇 가지 중요한 복잡도 종류는 DSPACE로 정의된다. 여기에는 다음이 포함된다.

 REG = DSPACE(O(1)), 여기서 REG는 정규 언어의 종류이다. 사실, REG = DSPACE(o(log log n))이다 (즉, 비정규 언어를 인식하는 데는  공간이 필요하다).Szepietowski (1994) p. 28

증명:
만약 s(n) = o(log log n)에 대해 비정규 언어 L ∈ DSPACE(s(n))가 존재한다고 가정하자. M을 공간 s(n)에서 L을 결정하는 튜링 기계라고 하자. 가정에 의해 L ∉ DSPACE(O(1))이므로, 임의의 에 대해 M의 입력 중 k보다 더 많은 공간을 요구하는 것이 존재한다.

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

S를 x에 대한 M의 모든 가능한 교차열의 집합이라고 하자. x에 대한 M의 교차열 길이는 최대 임을 주목하자: 만약 이보다 길다면, 일부 구성이 반복되어 M은 무한 루프에 빠질 것이다. 교차열의 모든 요소에 대해 가능한 경우도 최대 이므로, x에 대한 M의 서로 다른 교차열의 수는 다음과 같다.

비둘기집 원리에 따르면, 인 i < j인 인덱스가 존재하며, 여기서 와 는 각각 경계 i와 j에서의 교차열이다.

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

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

 L = DSPACE(O(log n))
 PSPACE = 
 EXPSPACE = 

기계 모델

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

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

위계 정리

공간 위계 정리는 모든 공간 구성 가능 함수 에 대해 공간 에서 결정 가능하지만 공간 에서는 결정 불가능한 어떤 언어 L이 존재함을 보여준다.

다른 복잡도 종류와의 관계
DSPACE는 비결정론적 튜링 기계의 메모리 공간 종류인 NSPACE의 결정론적 대응물이다. 사비치 정리Arora & Barak (2009) p. 86에 따르면, 다음과 같다.

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

.

결정론적 시간에 대한 훨씬 더 나은 시뮬레이션이 알려져 있다: 만약 이라면,

이는 윌리엄스의 결과로, 홉크로프트, 폴, 밸리언트의 이전  한계를 개선한 것이다.

반면에, 인 모든 함수에 대해,

.

 각주 




 외부 링크 
.

분류:복잡도 종류
분류:계산 자원