クラスR
【英】:class R
確率的な多項式時間アルゴリズムで解答を求めることができる問題のクラスの1つ. ある問題がクラスRに属するとは, 以下の条件を満たす確率的な多項式時間アルゴリズムが存在するときをいう:与えられた入力に対する答がYesの場合は, 必ずYesを出力し, 答がNoの場合は, 少なくとも確率1/2でNoを出力する. 例えば, 与えられた整数が合成数かどうかを判定する問題はクラスRに属する.
組合せ最適化: | オンラインアルゴリズム クラスMAX SNP クラスNC クラスR グラフ彩色問題 グレブナー基底 データ構造 |
- クラスRのページへのリンク