RE (計算複雑性理論)
RE は R より厳密に大きいことが知られており、Co-RE とは厳密に等しくないことが知られている。これらには次のような関係がある。
R = RE ∩ Co-RE {\displaystyle {\textbf {R}}={\textbf {RE}}\cap {\textbf {Co-RE}}}