PSPACEとは？ わかりやすく解説

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/28 03:19 UTC 版)

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

概要

PSPACE とはチューリングマシンによって多項式領域で解ける問題、すなわち使用するテープの長さが問題のサイズの多項式で収まる決定問題のクラスのことである（処理にかかる時間は問わない）。

多項式時間で解ける問題は当然ながらテープの使用回数も問題のサイズの多項式に比例するので P ⊆ PSPACE であることは自明である。またNP ⊆ PSPACE であることも証明されている。

このクラスに NP と同様の概念を当てはめたクラス、すなわち答えが与えられたときその検算が PSPACE になる NPSPACE というクラスを考えることもできるが、1970年 ウォルター・サヴィッチ（Walter Savitch）のサヴィッチの定理により PSPACE = NPSPACE ということが証明された。

PSPACE完全

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

その他の特性

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

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