PSPACE

PSPACE とは計算複雑性理論における複雑性クラスの一つ、Polynomial SPACE の略である。

概要

PSPACEはチューリングマシンによって解くことができ、かつ使用するテープの長さの上限が問題のサイズの多項式以下になる決定問題のクラスである。

P ⊆ PSPACE である。これは、多項式時間で解ける問題は、テープを読み書きする回数も問題のサイズの多項式回以下になることから明らかである。また、NP ⊆ PSPACE である。

NPSPACEは答えが与えられたときその検算が PSPACE になる決定問題である。 PSPACE = NPSPACEであることは、サヴィッチの定理の系として示される。

PSPACE完全

NP完全と同様に PSPACE に属する全ての問題から多項式時間変換可能であり、自らも PSPACE に属する問題を PSPACE完全 という。与えられた倉庫番ゲームが解を持つかの判定（一般倉庫番問題）や、n×n マスのリバーシや五目並べの与えられた局面から先手と後手のどちらに必勝法があるかの判定などが、PSPACE完全であることが知られている。

その他の特性

PSPACE は、交替性チューリング機械で多項式時間で解ける問題の集合としても定式化できる。この場合、APTIME あるいは単に AP とも呼ぶ。

PSPACE は、IP と呼ばれる対話型証明系で認識できる全言語にも対応する。