PSPACE-완전 문서 원본 보기

{{위키데이터 속성 추적}}
[[계산 복잡도 이론]]에서 '''PSPACE-완전'''은 [[복잡도 종류]]이다. [[판정 문제]]는 '''[[PSPACE]]'''에 들어 있고, 모든 PSPACE 문제가 이 문제로 [[다항 시간 다대일 환산]]될 수 있으면 PSPACE-완전이 된다. PSPACE-완전에 드는 문제는 PSPACE에서 가장 어려운 문제로 볼 수 있다. 이 문제들은 [[P (복잡도)|P]]나 [[NP (복잡도)|NP]]의 범위 바깥에 있을 것으로 보이지만, 아직 증명되지는 않았다. PSPACE-완전이 [[NC (복잡도)|NC]] 바깥에 있다는 것은 증명되었다.

[[NP-완전]]에 들어간다고 밝혀진 첫 문제는 [[충족 가능성 문제]]({{lang|en|SAT}})이다. 논리식이 참이 되도록 변수값을 할당할 수 있는지를 묻는 문제이다. 예를 들어, 다음 논리식을 참이 되게 할 수 있는지를 물을 수 있다.
: <math>\exists x_1 \, \exists x_2 \, \exists x_3 \, \exists x_4: (x_1 \lor \neg x_3 \lor x_4) \land (\neg x_2 \lor x_3 \lor \neg x_4)</math>

SAT 문제는 [[참 한정 불 식|TQBF]] 문제로 일반화할 수 있다. 이 문제는 가장 기본이 되는 PSPACE-완전 문제이다. 이 문제의 인스턴스는 전칭기호를 허용한다는 점을 빼면 SAT하고 비슷하다.
: <math>\exists x_1 \, \forall x_2 \, \exists x_3 \, \forall x_4: (x_1 \lor \neg x_3 \lor x_4) \land (\neg x_2 \lor x_3 \lor \neg x_4)</math>

NP-완전 문제는 전형적인 퍼즐과 닮았다는 점을 주목할 필요가 있다. 전형적인 퍼즐은 문제를 풀기 위해 값을 끼워맞출 방법이 있는지를 묻는다. PSPACE-완전 문제는 게임을 닮았다. 게임은 상대방이 할 수 있는 ''모든'' 이동에 대해, 내가 ''어떤'' 이동을 할 수 있는지, 내가 이기기 위해 ''어떤'' 이동을 할 수 있는지를 묻는다. 이 질문은 존재기호나 전칭기호를 대신한다. 수많은 퍼즐이 NP-완전이고, 수많은 게임이 PSPACE-완전인 것은 놀라운 일이 아니다.

PSPACE-완전에 들어가는 게임(''n'' × ''n'' 말판에서 할 수 있도록 일반화한 것)으로는 [[헥스 (보드 게임)|헥스]], [[리버시]], 솔리테어 게임인 [[러시아워 (보드 게임)|러시아워]], [[마작|마종]], [[소코반]], [[아토믹스]] 들이 있다. 일반화한 다른 게임으로 [[바둑]], [[체스]], [[체커]]는 [[EXPTIME-완전]]에 들어간다. 완벽한 두 사람이 한다면 게임은 매우 길어질 수 있기 때문에 PSPACE에 들어갈 것으로 보이지 않는다.

PSPACE-완전의 정의는 ''점근'' 복잡도에 기반하고 있다. 크기 ''n''인 문제를 푸는 데 걸리는 시간은 ''n''이 커짐에 따라 한없이 늘어나는 한계 안에 있다. 이는 8 × 8 말판에서 하는 체커 같은 게임은 절대로 PSPACE-완전일 수 없다는 뜻이다. (사실, 아주 큰 [[검색 테이블]]을 쓰면 상수 시간에 풀 수 있다.) 이 때문에 게임을 ''n'' × ''n'' 말판으로 일반화하여 다룬다. 체스 같은 몇몇 경우에는 이러한 확장은 인위적이고 주관적이기도 하다.

다른 PSPACE-완전 문제로는 주어진 문자열이 [[문맥-민감 문법]]으로 정의한 어떤 언어에 들어가는지를 판정하는 문제가 있다.

== 같이 보기 ==
* [[게임 복잡도]]

== 참고 문헌 ==

* {{서적 인용|저자 = [[마이클 사이프저]] | 연도 = 1997 | 제목 = Introduction to the Theory of Computation |url = https://archive.org/details/introductiontoth00sips | 출판사 = PWS Publishing |ISBN=0-534-94728-X| 장 = 8.3: PSPACE-완전성({{lang|en|PSPACE-completeness}}) | 페이지= [https://archive.org/details/introductiontoth00sips/page/283 283]-294 | 언어=영어}}
* {{서적 인용|저자 = [[마이클 게리]]와 [[데이비드 S. 존슨]] | 연도 = 1979 | 제목 = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]] | 출판사 = W.H. Freeman |ISBN=0-7167-1045-5| 장 = 7.4: 다항 공간 완전성({{lang|en|Polynomial Space Completeness}})| 페이지 = [https://archive.org/details/computersintract0000gare/page/170 170]-177 | 언어 = 영어}}

== 외부 링크 ==
* {{언어링크|en}} [http://www.ics.uci.edu/~eppstein/cgt/hard.html 게임과 퍼즐의 계산 복잡도]

{{복잡도 종류}}

[[분류:복잡도 종류]]