「クラスR」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: ''''【くらすあーる (class R)】''' 確率的な多項式時間アルゴリズムで解答を求めることができる問題のクラスの1つ. ある問題がクラ...') |
(相違点なし)
|
2007年7月11日 (水) 22:11時点における版
【くらすあーる (class R)】
確率的な多項式時間アルゴリズムで解答を求めることができる問題のクラスの1つ. ある問題がクラスRに属するとは, 以下の条件を満たす確率的な多項式時間アルゴリズムが存在するときをいう:与えられた入力に対する答がYesの場合は, 必ずYesを出力し, 答がNoの場合は, 少なくとも確率1/2でNoを出力する. 例えば, 与えられた整数が合成数かどうかを判定する問題はクラスRに属する.