PSPACE

계산 복잡도 이론에서 PSPACE는 결정론적 튜링 기계나 비결정론적 튜링 기계가 시간은 얼마든지 쓸 수 있고, 공간은 다항 공간만 써서 풀 수 있는 판정 문제들의 집합이다. 사비치 정리에 따르면 PSPACE는 NSPACE와 같기 때문에 튜링 기계가 결정론적이든 비결정론적이든 상관 없다.

문맥-민감 언어가 PSPACE의 진부분집합이다. 복잡도 종류 NL, P, NP, PSPACE, EXPSPACE가 갖는 관계는 이렇다:

${\displaystyle {\mathsf {NL}}\subseteq {\mathsf {P}}\subseteq {\mathsf {NP}}\subseteq {\mathsf {PSPACE}}}$

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

첫째 줄에 ${\displaystyle \subseteq }$ (부분집합) 기호가 세 개 있다. 셋 중 하나는 ${\displaystyle \subsetneq }$여야 하는데, 정확히 어느 것이 그런지는 알려진 바 없다. 수많은 사람들이 셋 모두 ${\displaystyle \subsetneq }$라고 추측하고 있다. P-NP 문제(두 번째 ${\displaystyle \subseteq }$가 ${\displaystyle \subsetneq }$인지 아닌지 묻는 문제)에 대한 해법에는 상금 백만 달러가 걸려 있다.

PSPACE에서 가장 어려운 문제들을 PSPACE-완전이라고 한다. PSPACE이고 NP는 아닐 것으로 예상되는 문제들을 알고 싶으면 PSPACE-완전을 보라.

다른 정의

PSPACE를 교대 튜링 기계가 다항 시간에 판정할 수 있는 문제의 집합으로 정의하기도 한다. APTIME 아니면 그냥 AP라고도 한다.

논리학에 바탕을 둔 정의는, 이차 논리에 추이 닫힘 연산을 더해서 표현할 수 있는 문제의 집합을 PSPACE라고 한다. 완전한 추이 닫힘일 필요는 없다. 가환 추이 폐포나 더 약간 형태도 충분하다. 이 연산자를 추가함으로써 PSPACE와 PH를 구분할 수 있(을지도 모르)게 된다.

복잡도 이론의 중요한 결과 중 하나는, PSPACE를 특정 대화형 증명 체계가 받아들일 수 있는 모든 언어로 특징지을 수 있다는 것이다. 이는 IP를 정의하는 특징이기도 하다. 이 체계에는 확률적 다항 시간 검증자가 주어진 언어에 어떤 문자열이 들어간다고 확신하게 하는 전능한 증명자가 있다. 문자열이 그 언어에 들어간다면, 검증자를 높은 확률로 확신시킬 수 있어야 한다. 그러나 들어가지 않는다면 낮은 확률로 예외가 생기는 경우를 빼고는 확신시킬 수 없어야 한다.

참고 문헌

• (영어) 복잡도 동물원 PSPACE 우리
• 마이클 사이프저 (1997). 〈8.2-8.3 (복잡도 종류 PSPACE, PSPACE-완전(The Class PSPACE, PSPACE-completeness))〉. 《Introduction to the Theory of Computation》 (영어). PWS Publishing. 281-294쪽. ISBN 0-534-94728-X.
• 크리스토스 파파디미트리우 (1993). 〈19: 다항 공간(Polynomial space)〉. 《Computational Complexity》 (영어) 1판. Addison Wesley. 455-490쪽. ISBN 0-201-53082-1. CS1 관리 - 추가 문구 (링크)