「R (計算複雑性理論)」の版間の差分
提供: miniwiki
ja>Minf 細 (テンプレートの追加) |
細 (1版 をインポートしました) |
(相違点なし)
| |
2018/8/19/ (日) 17:31時点における最新版
計算複雑性理論において、複雑性クラス R とは、チューリングマシンで解ける決定問題の集合であり、全ての帰納言語の集合に相当する。R はしばしば、「効率的に計算可能な」関数のクラスと言われる（チャーチ＝チューリングのテーゼ）。
任意の決定問題の解法として、その問題のリコグナイザと補問題のリコグナイザを並行して動作させ、どちらかが受容状態になるまで待つ方式を採用可能である。したがって、このクラスは RE を使って [math]RE \cap coRE[/math] と定義できる。