NSPACE

계산 복잡도 이론에서 비결정적 공간 또는 NSPACE는 비결정적 튜링 기계의 메모리 공간을 나타내는 연산 자원이다. 이것은 DSPACE의 비결정적 대응물이다.

NSPACE 측정은 비결정적 튜링 기계로 해답을 결정할 수 있는 복잡도 종류를 정의하는 데 사용된다. 복잡도 종류 NSPACE(f(n))는 비결정적 튜링 기계 M이 O(f(n)) 공간을 사용하여 풀 수 있는 결정 문제의 집합이며, 여기서 n은 입력의 길이이다.^[1]

몇 가지 중요한 복잡도 종류는 NSPACE로 정의할 수 있다. 다음이 포함된다.

• REG = DSPACE(O(1)) = NSPACE(O(1)), 여기서 REG는 정규 언어의 종류이다(비결정성은 상수 공간에서 능력을 추가하지 않는다).
• NL = NSPACE(O(log n))
• CSL = NSPACE(O(n)), 여기서 CSL은 문맥 의존 언어의 종류이다.
• PSPACE = NPSPACE = ⋃ k ∈ N N S P A C E ( n k ) {\displaystyle \bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(n^{k})}
• EXPSPACE = NEXPSPACE = ⋃ k ∈ N N S P A C E ( 2 n k ) {\displaystyle \bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(2^{n^{k}})}

이머만–셀렙체니 정리는 모든 함수 s(n) ≥ log n에 대해 NSPACE(s(n))가 여집합에 대해 닫혀 있음을 명시한다.

더 나아가 일반화된 것은 교대 튜링 기계로 정의되는 ASPACE이다.

NSPACE는 결정적 튜링 기계의 메모리 공간 종류인 DSPACE의 비결정적 대응물이다. 정의에 따라, 그리고 새비치 정리에 따라, 우리는 다음을 가진다.

D S P A C E [ s ( n ) ] ⊆ N S P A C E [ s ( n ) ] ⊆ D S P A C E [ ( s ( n ) ) 2 ] . {\displaystyle {\mathsf {DSPACE}}[s(n)]\subseteq {\mathsf {NSPACE}}[s(n)]\subseteq {\mathsf {DSPACE}}[(s(n))^{2}].}

NSPACE는 다음 정리를 통해 결정적 튜링 기계의 시간 복잡도를 결정하는 데에도 사용될 수 있다.

언어 L이 비결정적 TM에 의해 공간 S(n) (여기서 S(n) ≥ log n)에서 결정된다면, L이 결정적 TM에 의해 시간 O(C^S(n))에서 결정되도록 하는 상수 C가 존재한다.^[2]

DSPACE 측면에서 공간 복잡도를 측정하는 것은 주어진 알고리즘으로 주어진 계산 문제를 해결하는 데 실제 컴퓨터가 필요로 하는 총 메모리 양을 나타내므로 유용하다. 그 이유는 DSPACE가 실제 컴퓨터를 나타낼 수 있는 결정적 튜링 기계가 사용하는 공간 복잡도를 설명하기 때문이다. 반면에 NSPACE는 실제 컴퓨터를 나타내려고 할 때 유용하지 않은 비결정적 튜링 기계의 공간 복잡도를 설명한다. 이러한 이유로 NSPACE는 실제 응용 프로그램에서의 유용성이 제한적이다.

• 컴플렉시티 주: NSPACE(f(n)).