RP (計算複雑性理論)
計算複雑性理論における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 に属する問題の性質は変わらない。この定数はアルゴリズムの入力の内容や長さとは無関係である。
関連する複雑性クラス
[編集]RP の定義によれば、YES という解は常に正しく、NO という解はおおむね正しい。Co-RP クラスも同様に定義でき、NO という解が常に正しく、YES という解がおおむね正しい。換言すれば、Co-RP に相当するチューリング機械は YES となるべき入力は常に受理するが、NO となるべき入力は受理するか不受理かのどちらかとなる。BPP クラスは正解が YES であっても NO であっても間違う可能性のあるアルゴリズムに相当する。RP と Co-RP の積集合に相当するクラスを ZPP と呼ぶ。RP を R と呼ぶように、Co-RP を Co-R と呼ぶことがある。
PおよびNPとの関係
[編集]P は RP の部分集合であり、RP は NP の部分集合である。同様に、P は Co-RP の部分集合であり、Co-RP は Co-NP の部分集合である。これらの包含関係が真部分集合の関係であるかどうかは未だわかっていない。しかし、一般に P ≠ RP または RP ≠ NP であろうと考えられており、そうでないと P = NP ということになってしまい、これは一般には偽と考えられている（P≠NP予想）。RP = Co-RP であるかどうかも未だ明らかになっていないし、RP が NP と Co-NP の積集合の部分集合かどうかも明らかでない。
Co-RP に属する問題のうち、P に属さないと思われている問題の例として、整数に関する多変量計算式がゼロ多項式かどうかの判定問題がある。例えば、"x*x - y*y - (x+y)*(x-y)" はゼロ多項式だが、"x*x + y*y" はゼロ多項式ではない。
場合によってはより便利と思われる RP の定式化として、少なくともある(入力長に依らない)一定の割合の計算経路群が受理する場合に限って機械全体としてその入力を受理する非決定性チューリング機械が認識できる問題の集合という定義がある。一方、NP は少なくとも一つの計算経路だけが受理すればよいのであって、その割合は指数関数的に小さい。このように定式化すると、RP が NP の部分集合であることがより明確化される。
関連項目
[編集]
