多項式階層 - mrsekut-p

多項式階層

Polynomial hierarchy

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

https://gyazo.com/7b360477c11fb889dc3ad5410be3408a

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

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

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

雑に書いても、

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

となるのがわかる

https://gyazo.com/b3e5d54d3ffd993e1f280c39306aac5d https://ja.wikipedia.org/wiki/%E8%A4%87%E9%9B%91%E6%80%A7%E3%82%AF%E3%83%A9%E3%82%B9

比較

table:比較