프스페이스

계산 복잡성 이론에서 PSPACE는 다항식 공간을 사용하여 튜링 기계에 의해 해결될 수 있는 모든 의사결정 문제의 집합이다.null

형식 정의

만일 우리가 입력 크기 n의 일부 기능 t에 대해 O(t(n) 공간을 사용하는 튜링 기계에 의해 해결될 수 있는 모든 문제의 집합인 SPACE(t(n)을 가리킨다면, 우리는 PSPACE를 공식적으로^[1] 으로 정의할 수 있다.

${\displaystyle {\mathsf {PSPACE}=\bigcup _{k\in \mathb {N}{}{\mathsf {Space}}(n^{k})}$

PSPACE는 문맥에 민감한 언어 집합의 엄격한 상위 집합이다.null

튜링 기계를 비결정론적으로 사용할 수 있게 하는 것은 추가 전력을 추가하지 않는 것으로 밝혀졌다.사비치의 정리 때문에 ^[2]NPSPACE는 본질적으로 결정론적 튜링 기계가 훨씬 더 많은 공간을 필요로 하지 않고 비결정론적 튜링 기계를 시뮬레이션할 수 있기 때문에 PSPACE와 동등하다.^[3]또한 PSpace의 모든 문제의 보완도 PSPACE에 있는데, 이는 co-PSPACE = PSPACE라는 뜻이다.

타계급간의 관계

PSPACE와 복잡도 등급 NL, P, NP, PH, EXPTIME, EXPSPACE 사이에 다음과 같은 관계가 알려져 있다(주의: 엄격한 격납을 의미하는 ⊊은 as과 같지 않다).

${\displaystyle {\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}}}$

세 번째 줄부터는 첫 번째 줄과 두 번째 줄에서 둘 다 셋트 중 적어도 하나는 엄격해야 한다는 것을 따르게 되지만, 어느 쪽인지는 알 수 없다.모두가 엄격하다는 것이 널리 의심되고 있다.null

세 번째 줄의 함정은 둘 다 엄격한 것으로 알려져 있다.첫 번째는 직접적인 대각화(공간 계층화 정리, NL ⊊ NPSPACE)와 사비치의 정리를 통한 PSPACE = NPSPACE라는 사실에서 따온 것이다.두 번째는 단순히 우주 계층 구조 정리에서 따온 것이다.null

PSPACE에서 가장 어려운 문제는 PSPACE-완전한 문제들이다.PSPACE에는 있지만 NP에는 없는 것으로 의심되는 문제의 예는 PSPACE-완료를 참조하십시오.

마감 속성

PSPACE 클래스는 운영조합, 보완 및 클레인 스타에 의해 폐쇄된다.null

기타 특성화

PSPACE의 대체 특성화는 다항 시간(APTIME 또는 단지 AP라고도 함)에 있는 교번 튜링 기계에 의해 해독할 수 있는 문제들의 집합이다.^[4]null

기술 복잡성 이론에서 PSPACE의 논리적 특성은 타동적 폐쇄 운영자의 추가와 함께 2차 논리로 표현 가능한 문제들의 집합이라는 것이다.완전한 전이성 폐쇄는 필요하지 않다; 교환적 전이성 폐쇄와 심지어 약한 형태로도 충분하다.PSPACE와 PH를 구별하는 것은 (아마도) 이 연산자의 추가다.

복잡성 이론의 주요한 결과는 PSPACE가 클래스 IP를 정의하는 특정한 쌍방향 증명 시스템에 의해 인식될 수 있는 모든 언어로 특징지어질 수 있다는 것이다.이 시스템에는 무작위화된 다항식 시간 검증자가 문자열이 언어에 있음을 확신시키려고 하는 만능 프로베러가 있다.문자열이 언어에 있을 경우 높은 확률로 검증자를 설득할 수 있어야 하지만, 문자열이 언어에 없을 경우 낮은 확률 외에는 설득할 수 없어야 한다.null

PSPACE는 양자 복잡도 등급 QIP로 특징지어질 수 있다.^[5]null

또한 PSPACE는 닫힌 시간 곡선을 사용하는 고전적 컴퓨터에서 해결할 수 있는 문제인 P와_CTC 닫힌 시간 곡선을 사용하는 양자 컴퓨터에서 해결할 수 있는 문제인 BQP와_CTC 동일하다.^[6][7]null

PSPACE-완전성

언어 B는 PSpace에 있고 PSPACE-hard이면 PSPACE-complete이며, 이는 모든 A ∈ $PSPACE{\displaystyle {}_{}}$ A $≤$ ${\displaystyle P_{}}$ ${\displaystyle {}_{}}$ {\$displaystyle$A$\leq _${\text{\text$}$를 의미한다.$P}B$ 여기서 $A{\displaystyle }$ ${\displaystyle {}_{}}$ ${\displaystyle P_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle A\leq _{\text{$$P}}B}$은 다항 시간 다수가 A에서 B로 줄어든다는 것을 의미한다$$. PSPACE-완전한 문제는 PSPACE에서 가장 어려운 문제를 나타내기 때문에 PSPACE 문제를 연구하는 데 매우 중요하다.PSPACE-완전한 문제에 대한 간단한 해결책을 찾는 것은 모든 PSPACE 문제가 PSPACE-완전한 문제로 축소될 수 있기 때문에 PSPACE의 다른 모든 문제에 대한 간단한 해결책을 가지고 있다는 것을 의미한다.^[8]null

PSPACE-완전 문제의 예로는 정량화된 부울식 문제(일반적으로 QBF 또는 TQBF로 약칭되며, T는 "true"^[8]를 의미한다.null

참조

• Arora, Sanjeev; Barak, Boaz (2009). Computational complexity. A modern approach. Cambridge University Press. ISBN 978-0-521-42426-4. Zbl 1193.68112.
• Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. 섹션 8.2–8.3 (클래스 PSPACE, PSPACE-완전성), 페이지 281–294.
• Papadimitriou, Christos (1993). Computational Complexity (1st ed.). Addison Wesley. ISBN 0-201-53082-1. 19장: 다항식 공간, 페이지 455~490.
• Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). Thomson Course Technology. ISBN 0-534-95097-3. 8장: 공간 복잡성
• 복잡성 동물원: PSPACE