PSPACE

3. 다른 복잡도 종류와의 관계

새비치 정리에 의해, NPSPACE는 PSPACE와 동일하며, 이는 결정적 튜링 기계가 더 많은 공간을 필요로 하지 않고 비결정적 튜링 기계를 시뮬레이션할 수 있기 때문이다.^[3] 또한, PSPACE에 있는 모든 문제의 여집합도 PSPACE에 있다.

PSPACE와 복잡도 클래스인 NL, P, NP, PH, EXPTIME, EXPSPACE 간에는 다음과 같은 관계가 알려져 있다. (⊊는 엄격한 포함을 나타낸다.)

:$\backslash begin\{array\}\{l\}$

\mathsf{NL \subseteq P \subseteq NP \subseteq PH \subseteq PSPACE}\\

\mathsf{PSPACE \subseteq EXPTIME \subseteq EXPSPACE}\\

\mathsf{NL \subsetneq PSPACE \subsetneq EXPSPACE}\\

\mathsf{P\subsetneq EXPTIME}\end{array}

세 번째 줄에서 첫 번째와 두 번째 포함 관계 중 적어도 하나는 엄격해야 하지만, 어떤 것이 엄격한지는 알려져 있지 않다. 널리 모든 것이 엄격할 것으로 의심된다.

세 번째 줄의 포함 관계는 둘 다 엄격한 것으로 알려져 있다. 첫 번째는 공간 계층 정리와 새비치 정리를 통해 NPSPACE = PSPACE라는 사실에서 비롯된다. 두 번째는 공간 계층 정리에서 비롯된다.

PSPACE에서 가장 어려운 문제는 PSPACE-완전 문제이다.

4. 닫힘 성질

합집합, 여집합, 클레이니 스타 연산에 대해 닫혀 있다.

5. 대화형 증명 시스템

PSPACE는 특정 대화형 증명 체계(IP)로 인식 가능한 모든 언어로 특징지을 수 있다. 이 체계에서는 확률적 다항 시간 검증자와 전능한 증명자가 상호작용한다. 문자열이 그 언어에 들어간다면, 검증자를 높은 확률로 확신시킬 수 있어야 한다. 그러나 들어가지 않는다면 낮은 확률로 예외가 생기는 경우를 빼고는 확신시킬 수 없어야 한다.^[4]

PSPACE는 양자 복잡도 클래스 QIP로 특징지을 수 있다.^[5]

PSPACE는 또한 닫힌 시간꼴 곡선을 사용하는 고전 컴퓨터로 풀 수 있는 문제인 P_CTC와 닫힌 시간꼴 곡선을 사용하는 양자 컴퓨터로 풀 수 있는 문제인 BQP_CTC와도 같다.^[7]

6. PSPACE-완전

어떤 언어 ''B''가 PSPACE에 속하고 PSPACE-hard일 경우, 즉 모든 ''A'' ∈ PSPACE에 대해 $A\; \backslash leq\_\backslash text\{P\}\; B$가 성립할 때, ''PSPACE-완전''이라고 한다. 여기서 $A\; \backslash leq\_\backslash text\{P\}\; B$는 ''A''에서 ''B''로의 다항 시간 다대일 환원이 존재한다는 의미이다. PSPACE-완전 문제는 PSPACE에서 가장 어려운 문제이며, 이 문제에 대한 효율적인 해법은 PSPACE의 다른 모든 문제에 대한 효율적인 해법을 의미한다.^[8]

6. 1. PSPACE-완전 문제의 예시

참조

_[1] 서적 Arora & Barak 2009
_[2] 서적 Arora & Barak 2009
_[3] 서적 Arora & Barak 2009
_[4] 서적 Arora & Barak 2009
_[5] arXiv QIP = PSPACE 2009-07
_[6] 간행물 NP-complete problems and physical reality 2005-03
_[7] 간행물 Closed timelike curves make quantum and classical computing equivalent 2009
_[8] 서적 Arora & Barak 2009