Weblio辞書辞典>辞書･百科事典>RP_(計算複雑性理論)>RP_(計算複雑性理論)の1ﾍﾟｰｼﾞ目
RP_(計算複雑性理論)とは?
計算複雑性理論におけるRPとは､以下の3つの属性を持つ確率的ﾁｭｰﾘﾝｸﾞ機械で解ける問題の複雑性ｸﾗｽである｡
| RPｱﾙｺﾞﾘｽﾞﾑ（1回試行） |
|---|
| 生成される解 |
| 正解 | YES | NO |
| YES | ≥½ | ≤½ |
| NO | 0 | 1 |
| RPｱﾙｺﾞﾘｽﾞﾑ（n回試行） |
|---|
| 生成される解 |
| 正解 | YES | NO |
| YES | ≥1-½n | ≤½n |
| NO | 0 | 1 |
| Co-RPｱﾙｺﾞﾘｽﾞﾑ（1回試行） |
|---|
| 生成される解 |
| 正解 | YES | NO |
| YES | 1 | 0 |
| NO | ≤½ | ≥½ |
- 入力長に対して常に多項式時間かかる｡
- 正解が NO である場合､常に NO を返す｡
- 正解が YES である場合､確率 ½ 以上で YES を返す（そうでない場合､NO を返す）｡
換言すれば､そのｱﾙｺﾞﾘｽﾞﾑは､実行中に完全に無作為なｺｲﾝを投げているようなものである｡
このｱﾙｺﾞﾘｽﾞﾑが YES を返すのは､実際の答えが YES であるときだけである｡
したがって､ｱﾙｺﾞﾘｽﾞﾑが停止して YES を生成した場合､正解は必ず YES である｡
しかし､NO を返して停止する場合､実際の答えが何であるかはわからない｡
つまり､NO を返したとき､それは間違っている可能性がある｡
この複雑性ｸﾗｽを R と呼ぶこともあるが､一般に R と言えば帰納言語のｸﾗｽの名称として使われている｡
正解が YES であるとき､このｱﾙｺﾞﾘｽﾞﾑを n 回試行し､各試行には確率論的独立性があるとき､YES が少なくとも 1回返される確率は 1 - ½n 以上である｡
従って､100回試行すれば回答が間違っている確率は､宇宙線がｺﾝﾋﾟｭｰﾀのﾒﾓﾘの内容を破壊して計算結果を間違う可能性よりも低くなる｡
従って､乱数発生源があれば､RP に属するｱﾙｺﾞﾘｽﾞﾑの多くは極めて実用的となる｡
½ という割合は実際には任意の割合でよい｡
½ が 0 より大きく 1 より小さい任意の割合でありさえすれば､RP に属する問題の性質は変わらない｡
この定数はｱﾙｺﾞﾘｽﾞﾑの入力の内容や長さとは無関係である｡
RP の定義によれば､YES という解は常に正しく､NO という解はおおむね正しい｡
Co-RP ｸﾗｽも同様に定義でき､NO という解が常に正しく､YES という解がおおむね正しい｡
換言すれば､Co-RP に相当するﾁｭｰﾘﾝｸﾞ機械は YES となるべき入力は常に受理するが､NO となるべき入力は受理するか不受理かのどちらかとなる｡BPP ｸﾗｽは正解が YES であっても NO であっても間違う可能性のあるｱﾙｺﾞﾘｽﾞﾑに相当する｡RP と Co-RP の積集合に相当するｸﾗｽを ZPP と呼ぶ｡
楽に探せる!楽ﾜｰﾄﾞ
ﾍﾟｰｼﾞ(1/2)
次ﾍﾟｰｼﾞ≫