派生するクラス
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/11/14 08:31 UTC 版)
「Arthur–Merlinプロトコル」の記事における「派生するクラス」の解説
複雑性クラス一般に、補問題のクラスを定義できる。AMもまた、co-AMというクラスを考えることができる。形式的には次のように表される。 c o - A M = { L ¯ | L ∈ A M } {\displaystyle \mathbf {co{\text{-}}AM} =\{{\bar {L}}|L\in \mathbf {AM} \}} AM=co-AMかは知られていないが、2つのクラスは異なっていると予想されている。 絶対完全性(perfect completeness)は、確率1で完全性が満たされることであり、これを満たす言語のクラスを A M p c {\displaystyle \mathbf {AM} ^{pc}} と書くことにする。一方、絶対健全性(perfect soundness)は、確率1で健全性が満たされることであり、これを満たす言語のクラスを A M p s {\displaystyle \mathbf {AM} _{ps}} と書くことにする。AM及びAM[poly]は、絶対完全性の条件を課しても不変である。つまり、 A M p c = A M {\displaystyle \mathbf {AM} ^{pc}=\mathbf {AM} } A M [ poly ] p c = A M [ poly ] {\displaystyle \mathbf {AM} [{\text{poly}}]^{pc}=\mathbf {AM} [{\text{poly}}]} が成り立つ。一方で、 A M [ poly ] p s = N P {\displaystyle \mathbf {AM} [{\text{poly}}]_{ps}=\mathbf {NP} } である。
※この「派生するクラス」の解説は、「Arthur–Merlinプロトコル」の解説の一部です。
「派生するクラス」を含む「Arthur–Merlinプロトコル」の記事については、「Arthur–Merlinプロトコル」の概要を参照ください。
- 派生するクラスのページへのリンク
