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 = ${\displaystyle \bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(n^{k})}$
• EXPSPACE = NEXPSPACE = ${\displaystyle \bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(2^{n^{k}})}$

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

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

다른 복잡도 종류와의 관계

DSPACE

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

${\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는 실제 응용 프로그램에서의 유용성이 제한적이다.