完全問題とその他の特性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/27 03:33 UTC 版)
「PP (計算複雑性理論)」の記事における「完全問題とその他の特性」の解説
BPPとは異なり、PP は意味論的ではなく文法的なクラスである。任意の確率的機械は、何らかの PP に属する言語を認識する。一方、ある確率的機械の説明を与えられても、それが BPP に属する言語を認識できるかどうかは判定できない。 MAJSAT問題は、PP完全問題である。 PP は補集合と対称差について閉じており、和集合と共通部分についても閉じている。後者2つの証明は前者2つよりずっと難しく、約14年間未解決の問題となっていた。
※この「完全問題とその他の特性」の解説は、「PP (計算複雑性理論)」の解説の一部です。
「完全問題とその他の特性」を含む「PP (計算複雑性理論)」の記事については、「PP (計算複雑性理論)」の概要を参照ください。
ウィキペディア小見出し辞書の「完全問題とその他の特性」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 完全問題とその他の特性のページへのリンク
