クラスR

【くらすあーる (class R)】

確率的な多項式時間アルゴリズムで解答を求めることができる問題のクラスの1つ. ある問題がクラスRに属するとは, 以下の条件を満たす確率的な多項式時間アルゴリズムが存在するときをいう:与えられた入力に対する答がYesの場合は, 必ずYesを出力し, 答がNoの場合は, 少なくとも確率1/2でNoを出力する. 例えば, 与えられた整数が合成数かどうかを判定する問題はクラスRに属する.