PSPACE 복잡도 클래스 (PSPACE complexity class)

한 줄 정의: 다항 크기의 메모리 공간만 사용하면 실행 시간에는 제약이 없는 튜링 기계로 풀 수 있는 문제들의 복잡도 클래스.

쉽게 풀면

PSPACE는 '시간은 얼마가 걸리든 상관없지만 메모리는 문제 크기에 비례해서만 써야 한다'는 조건으로 풀 수 있는 문제들의 모임이다. P와 NP는 모두 PSPACE에 포함된다고 알려져 있는데, 이는 시간을 다항 시간으로 제한하면 자연히 사용하는 메모리도 다항 크기를 넘지 않기 때문이다. 두 명이 번갈아 두는 일반화된 체스나 바둑 같은 게임의 승패 판별 문제가 PSPACE-완전 문제의 대표적 예다.

왜 중요한가

PSPACE는 시간 복잡도 중심의 P, NP 계층과는 다른 축인 공간 복잡도를 기준으로 문제의 어려움을 분류하기 때문에, 계산복잡도 이론에서 문제의 본질적 난이도를 다각도로 이해하는 데 필수적인 개념으로 다뤄집니다. 게임 이론, 자동 계획(planning), 논리식 검증처럼 상호작용적이거나 순차적 의사결정이 필요한 문제들이 PSPACE-완전으로 분류되는 경우가 많아, 인공지능과 형식 검증 분야의 논문에서도 난이도 논의의 기준점으로 자주 인용됩니다.

논문에서는 이렇게 쓰입니다

"일반화된 보드게임의 최적 수를 판별하는 문제는 PSPACE-완전임이 알려져 있어, 다항 시간 알고리즘의 존재는 P=PSPACE 여부와 직결된다."

게임 이론이나 계획(planning) 문제의 계산 난이도가 NP보다 더 높은 수준임을 보일 때 사용된다.

"양화된 불리언 논리식의 참·거짓 판별 문제(QBF)는 PSPACE-완전 문제의 표준적인 예로, 여러 PSPACE 문제를 이 문제로 환원함으로써 난이도를 증명할 수 있다."

형식논리 및 자동추론 분야에서는 QBF 문제를 PSPACE-완전성 증명의 기준 문제로 흔히 활용한다.

"고전적 계획 수립(classical planning) 문제의 일반형은 PSPACE-완전으로 분류되며, 이는 실제 규모의 문제에서 완전 탐색 알고리즘이 비현실적임을 시사한다."

인공지능의 자동 계획 분야에서는 문제의 이론적 난이도를 근거로 근사 알고리즘이나 휴리스틱 탐색의 필요성을 정당화할 때 이 개념을 사용한다.

조금 더 깊게 보면

PSPACE는 사비치의 정리(Savitch's theorem)에 의해 비결정적 다항 공간 클래스인 NPSPACE와 동일하다는 것이 증명되어 있어, 공간 복잡도에서는 결정론과 비결정론의 구분이 시간 복잡도만큼 중요하지 않다는 특징을 보입니다. 또한 PSPACE-완전 문제를 다룰 때는 다항 시간 환원(polynomial-time reduction)을 이용해 어떤 문제가 다른 PSPACE 문제보다 최소한 그만큼 어렵다는 것을 보이는 방식이 표준적으로 쓰입니다. TQBF(참인 양화 불리언 논리식) 문제가 대표적인 PSPACE-완전 문제로 자주 인용됩니다.

주의할 점

P ⊆ NP ⊆ PSPACE라는 포함 관계는 증명되어 있지만, 이 포함이 진부분집합인지(즉 등호가 성립하지 않는지)는 아직 밝혀지지 않았다.