多項式階層との関係
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/11/14 08:31 UTC 版)
「Arthur–Merlinプロトコル」の記事における「多項式階層との関係」の解説
Boppana, Håstad & Zachos (1987)は次を示した。 c o - N P ⊆ A M ⇒ P H ⊆ A M {\displaystyle \mathbf {co{\text{-}}NP} \subseteq \mathbf {AM} \Rightarrow \mathbf {PH} \subseteq \mathbf {AM} } 一般に多項式階層は崩壊しないと考えられているので、co-NPがAMに包含されていないだろうと考えられている。また、別証明としてSchöning (1988)も知られている。 一般化すると、k≧1について Π k p ⊆ B P ⋅ Σ k p {\displaystyle \Pi _{k}^{p}\subseteq \mathbf {BP} \cdot \Sigma _{k}^{p}} (あるいは Σ k p ⊆ B P ⋅ Π k p {\displaystyle \Sigma _{k}^{p}\subseteq \mathbf {BP} \cdot \Pi _{k}^{p}} )ならば、 P H = B P ⋅ Σ k p = B P ⋅ Π k p {\displaystyle \mathbf {PH} =\mathbf {BP} \cdot \Sigma _{k}^{p}=\mathbf {BP} \cdot \Pi _{k}^{p}} である。
※この「多項式階層との関係」の解説は、「Arthur–Merlinプロトコル」の解説の一部です。
「多項式階層との関係」を含む「Arthur–Merlinプロトコル」の記事については、「Arthur–Merlinプロトコル」の概要を参照ください。
- 多項式階層との関係のページへのリンク
