RP (計算複雑性理論)
From Wikipedia, the free encyclopedia
計算複雑性理論におけるRP(randomized polynomial time)とは、以下の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 に属する問題の性質は変わらない。この定数はアルゴリズムの入力の内容や長さとは無関係である。
