PSPACE-완전

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

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

$\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})$

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

$\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})$

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》 (영어). PWS Publishing. 283-294쪽. ISBN 0-534-94728-X. 
• 마이클 게리와 데이비드 S. 존슨 (1979). 〈7.4: 다항 공간 완전성(Polynomial Space Completeness)〉. 《Computers and Intractability: A Guide to the Theory of NP-Completeness》 (영어). W.H. Freeman. 170-177쪽. ISBN 0-7167-1045-5. 

외부 링크

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