스페이스

계산 복잡도 이론에서, 비결정론적 공간 또는 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 = $\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(n^{k})$ $\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(n^{k})$ N $\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(n^{k})$ $\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(n^{k})$ P $\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(n^{k})$ C $\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(n^{k})$ ( $\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(n^{k})$ ) { $display$ style \ $bigcup$ _ { $k$ \ $in$ \ $mathbb$ { $N }$ { \ $mathsf$ { $NSPACE$ } （ $n^$ { $k$ } }
EXPSPACE = NEXPSPACE = $\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(2^{n^{k}})$ $\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(2^{n^{k}})$ N $\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(2^{n^{k}})$ $\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(2^{n^{k}})$ P $\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(2^{n^{k}})$ $\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(2^{n^{k}})$ E $\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(2^{n^{k}})$ ( $\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(2^{n^{k}})$ n $\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(2^{n^{k}})$ ) \ $displaystyle$ \ $bigcup$ _ { $k$ \ $in$ \ $mathbb$ { $N }$ { \ $mathsf$ { $NSPACE$ } } } ( $2$ ^ { $n^$ { $k$ } )

Immerman-Szelepcsényi 정리는 NSPACE(s(n))가 모든 $함수$ s $(n) log$ $log$ n에 대해 보완 하에 닫혀 있다고 기술한다.

또 다른 일반화는 ASPACE로, 교대 튜링 기계로 정의된다.

다른 복잡도 클래스와의 관계

DSPACE

NSPACE는 DSPACE의 비결정론적 대응물이며, 결정론적 튜링 기계상의 메모리 공간의 클래스입니다.먼저 정의에 의해, 다음으로 Savitch의 정리에 의해, 다음과 같은 것이 있습니다.

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

시간을

NSPACE는 또한 다음과 같은 정리에 의해 결정론적 튜링 기계의 시간 복잡성을 결정하기 위해 사용될 수 있다.

공간 S(n)(여기서 S(n)) log n)에서 비결정론적 TM에 의해 언어 L이 결정론적 ^[2]TM에 의해 결정되는 상수 C가^S(n) 존재한다.

제한 사항

DSPACE의 관점에서 공간 복잡성의 척도는 실제 컴퓨터가 주어진 알고리즘으로 주어진 계산 문제를 해결하기 위해 필요한 총 메모리 양을 나타내기 때문에 유용합니다.그 이유는 DSPACE가 실제 컴퓨터를 나타낼 수 있는 결정론적 튜링 기계에 의해 사용되는 공간의 복잡성을 설명하기 때문입니다.반면에 NSPACE는 실제 컴퓨터를 표현하려고 할 때 유용하지 않은 비결정론적 튜링 기계의 공간 복잡성을 기술한다.이러한 이유로 NSPACE는 실제 애플리케이션에 대한 유용성이 제한됩니다.

레퍼런스

^ Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). Course Technology. pp. 303–304. ISBN 978-0-534-95097-2.
^ Goddard, Wayne (2008). Introducing the Theory of Computation. Jones and Bartlett Publishers, Inc. p. 183. ISBN 978-0-7637-4125-9.

외부 링크

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

[1] Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). Course Technology. pp. 303–304. ISBN 978-0-534-95097-2.

[2] Goddard, Wayne (2008). Introducing the Theory of Computation. Jones and Bartlett Publishers, Inc. p. 183. ISBN 978-0-7637-4125-9.

[1]

[2]

v t 중요 복잡도 클래스(더 보기)
실현 가능하다고 생각되다	로그 타임 AC⁰ ACC⁰ TC⁰ L SL RL NL 엔씨 SC 참조 P P-완전 ZPP RP BPP BQP APX FP
실현 불가능한 것으로 생각됨	업. NP NP-완전 NP 하드 co-N co-NP-완전 오전 품질 관리 PH § P PP #P #P-완료 아이피 PSPACE PSPACE-완전
실현 불가능한 것으로 간주되다	제외 시간 넥스트 타임 엑스페이스 2회차 초등 홍보 R 재생 모든.
클래스 계층	다항식 계층 지수 계층 그르제고르치크 계층 산술적 계층 부울 계층
클래스 패밀리	DTime(DTIME) NTime(NTIME(NTIME) DSPACE 스페이스 확률적으로 확인할 수 있는 증거 인터랙티브 증명 시스템

Search