PSPACE完全

ウィキペディア

PSPACE

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/21 05:55 UTC 版)

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 と呼ばれる対話型証明系で認識できる全言語にも対応する。

表 話 編 歴 主な複雑性クラス
実用的な時間で解けるクラス	DLOGTIME AC0 ACC0 TC0 L SL RL NL NC SC CC P P完全 ZPP RP BPP BQP APX
実用的な時間で解けないと疑われているクラス	UP NP NP完全 NP困難 co-NP co-NP完全 AM QMA PH ⊕P PP #P #P完全 IP PSPACE
実用的な時間では解けないクラス	EXPTIME NEXPTIME EXPSPACE ELEMENTARY PR R RE ALL
クラス階層	多項式階層 指数階層 グジェゴルチク階層 算術的階層 ブーリアン階層
クラスの族	DTIME NTIME DSPACE NSPACE PCP 対話型証明系
一覧・ カテゴリ

ウィキペディア小見出し辞書

PSPACE完全

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

「PSPACE」の記事における「PSPACE完全」の解説

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