計算複雑性理論において、複雑性クラス R とは、チューリングマシンで解ける決定問題の集合であり、全ての帰納言語の集合に相当する。R はしばしば、「効率的に計算可能な」関数のクラスと言われる(チャーチ=チューリングのテーゼ)。
任意の決定問題の解法として、その問題のリコグナイザと補問題のリコグナイザを並行して動作させ、どちらかが受容状態になるまで待つ方式を採用可能である。したがって、このクラスは RE を使って と定義できる。
外部リンク
|
---|
実用的な時間で解けるクラス | |
---|
実用的な時間で解けないと疑われているクラス | |
---|
実用的な時間では解けないクラス | |
---|
クラス階層 | |
---|
クラスの族 | |
---|
一覧・ カテゴリ |