RP (計算複雑性理論)

RP（確率的多項式時間）についての概要

RPは、計算複雑性理論における重要なクラスであり、確率的チューリング機械が解決可能な問題のカテゴリを示しています。このクラスの特徴は、確率的な手法に基づいて問題の解を求めることができる点です。RPに属する問題は、以下の三つの基本的な条件を満たす必要があります。

1. 入力長に対する実行時間: RPにおけるアルゴリズムは、入力の長さに対して常に多項式時間で処理を行います。
2. NOの確実性: 正しい解がNOの場合、アルゴリズムは常にNOを返す必要があります。
3. YESの確率的返却: 正しい解がYESの場合、アルゴリズムは50%以上の確率でYESを返し、そうでない場合はNOを返します。

このように、RPにおけるアルゴリズムは、実行時に無作為にコインを投げるような動作をしながら解を出力します。たとえば、アルゴリズムがYESを出力した場合、それは実際に正しい解であることが確定します。しかし、NOを返した場合はその正確性が保証されないため、正解が何であるかは分かりません。

RPは他の計算クラスと一部関連しています。特に、RPというクラスは「R」とも呼ばれることがありますが、一般にRというと帰納言語のクラスを指します。また、RPの特性から、ある入力に対し成功が独立した試行で行われた場合、n回の試行の中で少なくとも1回はYESが得られる確率は1 - (1/2)^n以上です。たとえば、100回試行すれば、誤った結果を得る確率は非常に低くなるため、乱数生成器があればRPに属する多くのアルゴリズムが実用的なものとして動作します。

さらに、RPのYESの返却確率は実際には任意の割合が使用でき、50%という制約は特に重要ではありません。この割合はアルゴリズムの入力の内容や長さには依存しません。これにより、RPの多様性が広がります。

関連する複雑性クラス

RPの定義に基づくと、正しい解がYESであればその正確性は保証され、NOであればおおむね正しいとされます。これに関連するのがCo-RPというクラスです。Co-RPでは、NOという答えが常に正しく、YESの答えがあいまいになる特性を持ちます。さらに、BPP（確率的多項式時間）のクラスにおいては、いかなる正解でも間違う可能性があります。

RPおよびCo-RPの共通のクラスをZPPと呼び、RPはRの略称としても広く使われています。

PおよびNPとの関係

RPはPの部分集合であり、さらにRP自体はNPの部分集合でもあります。同様に、PはCo-RPの部分集合で、Co-RPもCo-NPの一部です。これらの関係が真の部分集合であるかどうかは未解決ですが、一般的にP≠RPまたはRP≠NPという考え方が支配的です。これは、もしP=NPが成り立つとすれば、それは広く誤りだと考えられているためです。また、RPとCo-RPが等しいかどうかも未だに解明されていません。

具体例として、Co-RPに属すると考えられるがPに入らない問題の一例は、整数に関する多変量計算式がゼロ多項式かどうかを判別する問題です。このようにRPやCo-RPの理解が広がることで、数学や計算理論におけるより深い考察が進むことになります。さらに、RPの定義の一つとして、非決定性チューリング機械がある一定の割合で計算経路を受理する場合に限り、その入力を受理するという見方も存在します。これは、NPは少なくとも1つの計算経路が受理されることを基にしているため、RPがNPの部分集合であることをより明確に示しています。

関連項目

このようにRPに関する理論は広範で、乱択アルゴリズムなどの関連するトピックについても興味深い研究が進められています。

もう一度検索