Loading article…
計算複雑性理論において、ランダム化多項式時間（RP）とは、以下の特性を持つ確率的チューリングマシンが存在する決定問題の複雑性クラスのことである。
つまり、このアルゴリズムは実行中に真にランダムなコインを投げることが許されている。アルゴリズムがYESを返すことができるのは、実際の答えがYESの場合のみである。したがって、アルゴリズムが終了してYESを出力した場合、正解は間違いなくYESである。しかし、アルゴリズムは実際の答えに関係なくNOで終了する可能性がある。つまり、アルゴリズムがNOを返した場合、それは間違っている可能性がある。
一部の著者はこのクラスをRと呼んでいるが、この名前は再帰言語のクラスに対してより一般的に使用されている。
正解がYESで、アルゴリズムをn回実行し、各実行結果が統計的に互いに独立している場合、少なくとも1回はYESを返す確率は1-2 - n以上になります。つまり、アルゴリズムを100回実行した場合、毎回間違った答えを返す確率は、宇宙線がアルゴリズムを実行しているコンピュータのメモリを破損させる確率よりも低くなります。[ 1 ]この意味で、乱数源が利用可能であれば、RPのほとんどのアルゴリズムは非常に実用的です。
定義中の分数1/2は任意の値です。1/2を1未満の任意の非ゼロ定数確率に置き換えても、集合RPには全く同じ問題が含まれます。ここで定数とは、アルゴリズムへの入力に依存しないことを意味します。
言語LがRPに属するのは、確率的チューリング マシンMが存在し、
あるいは、RPは決定性チューリングマシンのみを使用して定義することもできます。言語LがRPに含まれるのは、多項式pと決定性チューリングマシンMが存在し、以下の条件を満たす場合に限ります。
この定義では、文字列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という名前を使用することもあります。
PはRPの部分集合であり、RP はNPの部分集合である。同様に、 Pはco-RPの部分集合であり、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の部分集合であることが明らかになる。
