PSPACE
PSPACE とはチューリングマシンによって多項式領域で解ける問題、すなわち使用するテープの長さが問題のサイズの多項式で収まる決定問題のクラスのことである(処理にかかる時間は問わない)。
多項式時間で解ける問題は当然ながらテープの使用回数も問題のサイズの多項式に比例するので P ⊆ PSPACE であることは自明である。またNP ⊆ PSPACE であることも証明されている。
このクラスに NP と同様の概念を当てはめたクラス、すなわち答えが与えられたときその検算が PSPACE になる NPSPACE というクラスを考えることもできるが、1970年 ウォルター・サヴィッチ(Walter Savitch)のサヴィッチの定理により PSPACE = NPSPACE ということが証明された。