RPランダム化多項式時間は、計算複雑性理論の複雑性クラスであり、確率的チューリングマシンが次のような性質を持つ問題である。ƒ常に入力サイズの多項式時間で実行されるƒ正解がNOの場合、常にNOを返すƒ正解がYESの場合、少なくとも1/2の確率でYESを返す。 アルゴリズムがYESを返すことができる唯一のケースは、実際の答えがYESの場合です; したがって、アルゴリズムが終了してYESを生成する場合、正しい答えは間違いなくYESですが、実際の答えに関係なく、アルゴリズムはNOで終了できます。 つまり、アルゴリズムがNOを返す場合、それは間違っている可能性があります。一部の著者はこのクラスをRと呼んでいますが、この名前は再帰言語のクラスでより一般的に使用されています。正解がYESで、アルゴリズムが他の実行の結果と統計的に独立してn回実行された場合、少なくとも1−2−の確率で少なくとも1回はYESを返します。 したがって、アルゴリズムが100回実行された場合、毎回間違った答えを与える可能性は、宇宙線がアルゴリズムを実行しているコンピュータのメモリを破損した可能性よりも低くなります。 この意味で、乱数のソースが利用可能であれば、RPのほとんどのアルゴリズムは非常に実用的です。

続きを見る”