PSPACE

1. 개요

PSPACE는 튜링 머신으로 다항 공간 내에 풀 수 있는 모든 결정 문제의 집합이다. PSPACE는 비결정적 튜링 머신을 결정적 튜링 머신으로 시뮬레이션할 수 있다는 사비치 정리에 의해 NPSPACE와 동일하며, co-PSPACE와도 같다. PSPACE는 P, NP, PH를 포함하며 EXPTIME에 포함된다. PSPACE에서 가장 어려운 문제는 PSPACE-완전 문제이며, 수량화된 부울식 문제(QBF)가 그 예시이다. PSPACE는 교대 튜링 머신으로 다항 시간 내에 풀 수 있는 문제의 집합(APTIME 또는 AP), 대화형 증명 시스템(IP), 양자 복잡도 클래스 QIP로도 특징지을 수 있다.

2. 정의

만약 입력 크기 n에 대한 함수 f에 대해 O(f(n)) 공간을 사용하여 튜링 기계로 풀 수 있는 모든 문제의 집합을 SPACE(f(n))으로 표기한다면, PSPACE는 다음과 같이 공식적으로 정의할 수 있다.

:$\backslash mathsf\{PSPACE\}\; =\; \backslash bigcup\_\{k\backslash in\backslash mathbb\{N\}\}\; \backslash mathsf\{SPACE\}(n^k).$

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

PSPACE는 튜링 머신에 의해 다항식 공간으로 풀 수 있는 문제, 즉 사용하는 테이프의 길이가 문제 크기의 다항식으로 억제되는 결정 문제의 클래스이다. 다항식 시간으로 풀 수 있는 문제는 테이프 사용 횟수도 문제 크기의 다항식에 비례하므로 P ⊆ PSPACE이며, NP ⊆ PSPACE임도 증명되어 있다.

2.1. 다른 정의

PSPACE는 교대 튜링 기계가 다항 시간에 판정할 수 있는 문제의 집합으로 정의되기도 하며, APTIME 또는 AP라고도 부른다.

논리학적 관점에서 PSPACE는 이차 논리에 추이 닫힘 연산자를 추가하여 표현할 수 있는 문제의 집합이다. 완전한 추이 닫힘은 필요하지 않으며, 가환 추이 닫힘이나 더 약한 형태로도 충분하다. 이러한 연산자를 추가하면 PSPACE를 PH와 구별할 수 있을지도 모른다.

복잡도 이론에서 중요한 결과 중 하나는 PSPACE가 IP를 정의하는 특징인, 특정 대화형 증명 체계에서 받아들일 수 있는 모든 언어로 특징지을 수 있다는 것이다. 이 체계에서는 전능한 증명자가 확률적 다항 시간 검증자에게 주어진 문자열이 특정 언어에 속한다고 확신시키려 한다. 문자열이 해당 언어에 속하면 증명자는 높은 확률로 검증자를 설득할 수 있어야 하지만, 그렇지 않은 경우에는 낮은 확률로만 설득할 수 있어야 한다.

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

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

새비치 정리에 의해, NPSPACE는 PSPACE와 동일하며, 이는 결정적 튜링 기계가 더 많은 공간을 필요로 하지 않고 비결정적 튜링 기계를 시뮬레이션할 수 있기 때문이다. 또한, 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)로 인식 가능한 모든 언어로 특징지을 수 있다. 이 체계에서는 확률적 다항 시간 검증자와 전능한 증명자가 상호작용한다. 문자열이 그 언어에 들어간다면, 검증자를 높은 확률로 확신시킬 수 있어야 한다. 그러나 들어가지 않는다면 낮은 확률로 예외가 생기는 경우를 빼고는 확신시킬 수 없어야 한다.

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

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

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의 다른 모든 문제에 대한 효율적인 해법을 의미한다.

6.1. PSPACE-완전 문제의 예시

PSPACE-완전 문제의 예시로는 수량화된 부울식 문제(일반적으로 QBF 또는 TQBF로 축약되며, T는 "true"를 의미한다)가 있다.

NP 완전과 마찬가지로 PSPACE에 속하는 모든 문제로부터 다항 시간 환산 가능한 문제이며, 스스로도 PSPACE에 속하는 문제를 PSPACE 완전이라고 한다. 창고 정비원 게임(일반 창고 정비원 문제)이 해를 갖는지 판정이나, n×n 칸의 오델로나 오목의 주어진 국면에서 선공과 후공 중 어느 쪽에 필승법이 있는지 판정하는 문제 등이 PSPACE 완전으로 알려져 있다.