他の複雑性クラスとの関係
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/11/14 09:13 UTC 版)
「PCP (計算複雑性理論)」の記事における「他の複雑性クラスとの関係」の解説
単純な特殊ケース（poly は多項式的な量であることを意味し、log は対数的な量であることを意味する）: PCP (0, 0) =P PCP (poly, 0) = Co-RP PCP (0, poly) = NP その他の特筆すべき例: PCP (poly, poly) = NEXP もし NP = PCP (o(log), o(log)) なら NP = P となる。 NP = PCP (log, poly) PCP定理によると、NP = PCP (O(log n), O(1)) である。これは、近似アルゴリズムのために計算困難性を証明するのに役立つ。
※この「他の複雑性クラスとの関係」の解説は、「PCP (計算複雑性理論)」の解説の一部です。
「他の複雑性クラスとの関係」を含む「PCP (計算複雑性理論)」の記事については、「PCP (計算複雑性理論)」の概要を参照ください。
ウィキペディア小見出し辞書の「他の複雑性クラスとの関係」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 他の複雑性クラスとの関係のページへのリンク
