算術的階層の計算複雑性理論版みたいなやつ

これが丸々算術的階層の\Delta_0に含まれる

A\to Bは、A\subseteq Bを表す

多項式階層は、算術的階層の\Delta_0に含まれる

中央の横長のクラスPSPACEが、一番上の「決定問題」の中にいることがわかる

雑に書いても、

P\subsetPH(多項式階層)\subset \mathrm{PSPACE}\subset決定問題

となるのがわかる

比較

関連