「クラスR」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: ''''【くらすあーる (class R)】''' 確率的な多項式時間アルゴリズムで解答を求めることができる問題のクラスの1つ. ある問題がクラ...') |
Albeit-Kun (トーク | 投稿記録) |
||
| (他の1人の利用者による、間の1版が非表示) | |||
| 2行目: | 2行目: | ||
確率的な多項式時間アルゴリズムで解答を求めることができる問題のクラスの1つ. ある問題がクラスRに属するとは, 以下の条件を満たす確率的な多項式時間アルゴリズムが存在するときをいう:与えられた入力に対する答がYesの場合は, 必ずYesを出力し, 答がNoの場合は, 少なくとも確率1/2でNoを出力する. 例えば, 与えられた整数が合成数かどうかを判定する問題はクラスRに属する. | 確率的な多項式時間アルゴリズムで解答を求めることができる問題のクラスの1つ. ある問題がクラスRに属するとは, 以下の条件を満たす確率的な多項式時間アルゴリズムが存在するときをいう:与えられた入力に対する答がYesの場合は, 必ずYesを出力し, 答がNoの場合は, 少なくとも確率1/2でNoを出力する. 例えば, 与えられた整数が合成数かどうかを判定する問題はクラスRに属する. | ||
| + | |||
| + | [[Category:組合せ最適化|くらすあーる]] | ||
2008年11月8日 (土) 19:41時点における最新版
【くらすあーる (class R)】
確率的な多項式時間アルゴリズムで解答を求めることができる問題のクラスの1つ. ある問題がクラスRに属するとは, 以下の条件を満たす確率的な多項式時間アルゴリズムが存在するときをいう:与えられた入力に対する答がYesの場合は, 必ずYesを出力し, 答がNoの場合は, 少なくとも確率1/2でNoを出力する. 例えば, 与えられた整数が合成数かどうかを判定する問題はクラスRに属する.