R (計算複雑性理論)のソースを表示

[[計算複雑性理論]]において、[[複雑性クラス]] '''R''' とは、[[チューリングマシン]]で解ける[[決定問題]]の集合であり、全ての[[帰納言語]]の集合に相当する。'''R''' はしばしば、「効率的に計算可能な」関数のクラスと言われる（[[チャーチ＝チューリングのテーゼ]]）。

任意の決定問題の解法として、その問題の[[有限オートマトン#アクセプタ / リコグナイザ|リコグナイザ]]と補問題のリコグナイザを並行して動作させ、どちらかが受容状態になるまで待つ方式を採用可能である。したがって、このクラスは '''[[RE (計算複雑性理論)|RE]]''' を使って <math>RE \cap coRE</math> と定義できる。

== 外部リンク ==
* [http://qwiki.caltech.edu/wiki/Complexity_Zoo#re Complexity Zoo]
{{Computer-stub}}

{{複雑性クラス}}

[[Category:計算複雑性理論]]
[[Category:数学に関する記事]]