多項式階層内のクラス間の関係
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/01/13 15:58 UTC 版)
「多項式階層」の記事における「多項式階層内のクラス間の関係」の解説
定義から、次のような関係が成り立つ。 Σ i P ⊆ Δ i + 1 P ⊆ Σ i + 1 P {\displaystyle \Sigma _{i}^{\rm {P}}\subseteq \Delta _{i+1}^{\rm {P}}\subseteq \Sigma _{i+1}^{\rm {P}}} Π i P ⊆ Δ i + 1 P ⊆ Π i + 1 P {\displaystyle \Pi _{i}^{\rm {P}}\subseteq \Delta _{i+1}^{\rm {P}}\subseteq \Pi _{i+1}^{\rm {P}}} Σ i P = c o Π i P {\displaystyle \Sigma _{i}^{\rm {P}}={\rm {co}}\Pi _{i}^{\rm {P}}} 真の包含であることがわかっている算術的階層や解析的階層とは異なり、これらの包含関係が厳密かどうか（真部分集合かどうか）は未解決の問題である。ただし、これら全てが厳密な包含関係であると広く信じられている。もしこれが成り立たず、ある k について Σ k P = Σ k + 1 P {\displaystyle \Sigma _{k}^{\rm {P}}=\Sigma _{k+1}^{\rm {P}}} すなわち Σ k P = Π k P {\displaystyle \Sigma _{k}^{\rm {P}}=\Pi _{k}^{\rm {P}}} となることを「多項式階層が第 k 層で潰れる」と言う。もしそうなら全ての i > k {\displaystyle i>k} について Σ i P = Σ k P {\displaystyle \Sigma _{i}^{\rm {P}}=\Sigma _{k}^{\rm {P}}} となる。特に P = NP なら、階層は完全に潰れる。 多項式階層にある全クラス群の和集合を PH と書く。 多項式時間階層は、指数時間階層や算術的階層に似ている。 PH が PSPACE に包含されることは知られているが、2つのクラスが等しいかどうかは不明である。この問題を言い換えると、PH = PSPACE であるならば、二階述語論理に推移閉包演算子を追加しても強化されないことになる。 もし多項式階層が完全問題を含むなら、どこかの層に潰れる。PSPACE完全問題は存在するので、PSPACE = PH ならば、PSPACE完全問題が Σ k P {\displaystyle \Sigma _{k}^{\rm {P}}} -完全問題だということになるので、多項式階層は潰れる。 多項式階層の各層については ≤ m P {\displaystyle \leq _{\rm {m}}^{\rm {P}}} -完全問題（多項式時間多対一還元において完全な問題）がある。さらに、多項式階層の各層は ≤ m P {\displaystyle \leq _{\rm {m}}^{\rm {P}}} -還元において閉じている。つまり、この階層上のあるクラス C {\displaystyle {\mathcal {C}}} と言語 L ∈ C {\displaystyle L\in {\mathcal {C}}} があるとき、 A ≤ m P L {\displaystyle A\leq _{\rm {m}}^{\rm {P}}L} ならば、同時に A ∈ C {\displaystyle A\in {\mathcal {C}}} である。これらの事実から、 K i {\displaystyle K_{i}} を Σ i P {\displaystyle \Sigma _{i}^{\rm {P}}} の完全問題としたとき、 Σ i + 1 P = ( Σ i P ) K i {\displaystyle \Sigma _{i+1}^{\rm {P}}=\left(\Sigma _{i}^{\rm {P}}\right)^{K_{i}}} と Π i + 1 P = ( Π i P ) K i c {\displaystyle \Pi _{i+1}^{\rm {P}}=\left(\Pi _{i}^{\rm {P}}\right)^{K_{i}^{\rm {c}}}} が成り立つことがわかる。実際、 Σ 2 P = N P S A T {\displaystyle \Sigma _{2}^{\rm {P}}={\rm {NP}}^{\rm {SAT}}} である。言い換えれば、言語を C {\displaystyle {\mathcal {C}}} に含まれる何らかの神託機械に基づいて定義したとき、それを C {\displaystyle {\mathcal {C}}} の完全問題に基づいて定義したと見なすことができる。完全問題は従って、それが完全であるとするクラスを代表していると見なせる。
※この「多項式階層内のクラス間の関係」の解説は、「多項式階層」の解説の一部です。
「多項式階層内のクラス間の関係」を含む「多項式階層」の記事については、「多項式階層」の概要を参照ください。
- 多項式階層内のクラス間の関係のページへのリンク
