# PSPACE-완전

### 위키백과 ― 우리 모두의 백과사전.

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

NP-완전에 들어간다고 밝혀진 첫 문제는 불 만족성 문제(SAT)이다. 논리식이 참이 되도록 변수값을 할당할 수 있는지를 묻는 문제이다. 예를 들어, 다음 논리식을 참이 되게 할 수 있는지를 물을 수 있다.

SAT 문제는 TQBF 문제로 일반화할 수 있다. 이 문제는 가장 기본이 되는 PSPACE-완전 문제이다. 이 문제의 인스턴스는 전칭기호를 허용한다는 점을 빼면 SAT하고 비슷하다.

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

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

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

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

## [편집] 더 보기

- 게임 복잡도

## [편집] 참고문헌

- 마이클 사이프저 (1997). “8.3: PSPACE-완전성(PSPACE-completeness)”, Introduction to the Theory of Computation (in 영어). PWS Publishing, 283-294. ISBN 0-534-94728-X.
- 마이클 게리와 데이비드 존슨 (1979). “7.4: 다항 공간 완전성(Polynomial Space Completeness)”, Computers and Intractability: A Guide to the Theory of NP-Completeness (in 영어). W.H. Freeman, 170-177. ISBN 0-7167-1045-5.

## [편집] 외부 링크

- ((영어)) 게임과 퍼즐의 계산 복잡도

원본 주소 ‘http://ko.wikipedia.org../../../p/s/p/PSPACE-%EC%99%84%EC%A0%84_0ca0.html’

분류: 복잡도 종류

##### Views

- 문서
- 토론
- 현재 버전

##### 찾기

##### 다른 언어

- English
- Español