RP (複雑さ)

計算複雑性理論において、ランダム化多項式時間( RP ) は、以下の特性を持つ確率的チューリング マシンが存在する問題の複雑性クラスです。

• 入力サイズに応じて常に多項式時間で実行される
• 正解がNOの場合、常にNOを返します。
• 正解が YES の場合、少なくとも 1/2 の確率で YES を返します (それ以外の場合は NO を返します)。

言い換えると、アルゴリズムは実行中に完全にランダムにコインを投げることができます。アルゴリズムが YES を返すことができる唯一のケースは、実際の答えが YES である場合です。したがって、アルゴリズムが終了して YES を生成した場合、正しい答えは間違いなく YES です。ただし、実際の答えに関係なく、アルゴリズムは NO で終了する場合があります。つまり、アルゴリズムが NO を返す場合、間違っている可能性があります。

このクラスをRと呼ぶ著者もいますが、この名前は再帰言語のクラスに対してより一般的に使用されています。

正解が YES で、アルゴリズムがn回実行され、各実行の結果が他の実行から統計的に独立している場合、少なくとも1 − 2 ^{− n の}確率で少なくとも 1 回は YES を返します。したがって、アルゴリズムが 100 回実行された場合、毎回間違った答えを返す可能性は、宇宙線がアルゴリズムを実行しているコンピューターのメモリを破壊する可能性よりも低くなります。^[1]この意味で、乱数ソースが利用できる場合、RPのほとんどのアルゴリズムは非常に実用的です。

定義内の分数 1/2 は任意です。1/2 を 1 未満の任意の定数非ゼロ確率に置き換えても、セットRPにはまったく同じ問題が含まれます。ここで定数とは、アルゴリズムへの入力に依存しないことを意味します。

言語LがRPに属するのは、確率的チューリングマシン Mが存在し、

• Mはすべての入力に対して多項式時間で実行される
• L内のすべてのxに対して、M は1/2 以上の確率で 1 を出力する。
• Lに含まれないすべてのxに対して、Mは0を出力する。

あるいは、RPは決定性チューリングマシンのみを使って定義することもできる。言語LがRPに属するのは、多項式pと決定性チューリングマシンMが存在し、

• Mはすべての入力に対して多項式時間pで実行される
• L内のすべてのxについて、長さp (| x |)の文字列yのうち、 ⁠ ⁠ を満たすものの割合は1/2 以上である。${\displaystyle M(x,y)=1}$
• Lに含まれないすべてのxと、長さがp (| x |)のすべての文字列yについて、 ⁠ ⁠${\displaystyle M(x,y)=0}$

この定義では、文字列y は、確率的チューリング マシンが行うランダムなコイン投げの出力に対応します。一部のアプリケーションでは、確率的チューリング マシンについて言及していないため、この定義の方が適しています。

RPの定義では、YES の回答は常に正しく、NO の回答は間違っている可能性があるとされています。これは、YES インスタンスが NO の回答を返す可能性があるためです。複雑性クラスco-RP は、YES の回答が間違っている可能性がある一方で、NO の回答は常に正しいという補完関係です。

クラスBPP は、 YES と NO の両方のインスタンスで誤った回答を返す可能性のあるアルゴリズムを記述するため、RPとco-RP の両方が含まれます。 RPとco-RP の集合の共通部分はZPPと呼ばれます。 RP がRと呼ばれることがあるのと同様に、一部の著者はco-RPではなくco-Rという名前を使用します。

コンピュータサイエンスにおける未解決の問題:

⁠ ⁠${\displaystyle {\mathsf {P}}{\overset {?}{=}}{\mathsf {RP}}}$

(コンピュータサイエンスにおける未解決の問題)

P はRPのサブセットであり、 RP はNPのサブセットです。同様に、 P はco-RPのサブセットであり、 co-NPのサブセットです。これらの包含が厳密であるかどうかは不明です。ただし、一般に信じられているP = BPPという推測が正しい場合、 RP、 co-RP、およびP は一致します（すべて等しい）。さらにP ≠ NPと仮定すると、 RP はNPに厳密に含まれることになります。 RP = co-RPであるかどうか、またはRP がNPとco-NPの共通部分のサブセットである不明ですが、これはP = BPPによって示唆されます。

現在Pに含まれることが知られていないco-RPの問題の自然な例としては、多項式恒等式テストがあります。これは、整数上の与えられた多変数算術式がゼロ多項式であるかどうかを判断する問題です。たとえば、x · x − y · y − ( x + y )·( x − y )はゼロ多項式ですが、 x · x + y · yはゼロ多項式ではありません。

RPの別の特徴付けは、非決定性チューリング マシンによって認識可能な問題のセットであり、これは、入力サイズに関係なく、計算パスの少なくとも一定の割合が受け入れる場合にのみマシンが受け入れるというものです。一方、 NPでは、受け入れパスは 1 つだけ必要であり、これはパスの指数関数的に小さい割合を構成する可能性があります。この特徴付けにより、 RPがNPのサブセットであるという事実が明らかになります。

• ランダム化アルゴリズム
• ＢＰＰ
• ジップ

• 複雑性動物園でのRP