R（複雑性）

計算複雑性理論において、Rはチューリングマシンで解ける決定問題のクラスであり、すべての再帰言語（決定可能言語とも呼ばれる）の集合である。

Rは、以下の意味で、すべての計算可能な関数の集合と同等である。

• 決定問題がRに含まれるのは、その指示関数が計算可能である場合に限る。
• 総関数が計算可能であるのは、そのグラフがRに含まれる場合に限る。

認識器と共認識器が存在する問題であれば、結果が得られるまでそれらを交互に繰り返すだけで解決できるため、クラスはRE ∩ co-REに等しくなります。

• Blum, Lenore、Mike Shub、およびSteve Smale、（1989）、「実数上の計算と複雑性の理論について：NP完全性、再帰関数、およびユニバーサルマシン」、Bulletin of the American Mathematical Society、新シリーズ、21（1）：1-46。

複雑性動物園：クラスR