RE (計算複雑性理論)

計算複雑性理論において、複雑性クラス RE（recursively enumerable）とは、チューリングマシン（Turing machine）で有限時間内に 'yes' という解を得られる決定問題の集合である。逆に解が 'no' であった場合、マシンが停止するかどうかも保証されない。

RE はまた、解が 'yes' であるような問題をチューリングマシンを使ってリストアップ可能な決定問題のクラスでもある。このため 'enumerable'（枚挙可能）と呼ばれる。

解が 'no' の場合に同様の性質となるクラスを Co-RE と呼ぶ。

RE の各要素は帰納的可算集合（recursively enumerable set）である。

他のクラスとの関係

RE は R より厳密に大きいことが知られており、Co-RE とは厳密に等しくないことが知られている。これらには次のような関係がある。

${\textbf {R}}={\textbf {RE}}\cap {\textbf {Co-RE}}$

外部リンク

• Complexity Zoo: Class RE.