関連する複雑性クラス
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/14 03:55 UTC 版)
「RP (計算複雑性理論)」の記事における「関連する複雑性クラス」の解説
RP の定義によれば、YES という解は常に正しく、NO という解はおおむね正しい。Co-RP クラスも同様に定義でき、NO という解が常に正しく、YES という解がおおむね正しい。換言すれば、Co-RP に相当するチューリング機械は YES となるべき入力は常に受理するが、NO となるべき入力は受理するか不受理かのどちらかとなる。BPP クラスは正解が YES であっても NO であっても間違う可能性のあるアルゴリズムに相当する。RP と Co-RP の積集合に相当するクラスを ZPP と呼ぶ。RP を R と呼ぶように、Co-RP を Co-R と呼ぶことがある。
※この「関連する複雑性クラス」の解説は、「RP (計算複雑性理論)」の解説の一部です。
「関連する複雑性クラス」を含む「RP (計算複雑性理論)」の記事については、「RP (計算複雑性理論)」の概要を参照ください。
ウィキペディア小見出し辞書の「関連する複雑性クラス」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 関連する複雑性クラスのページへのリンク
