RE (complexity)

From Wikipedia, the free encyclopedia

RE (recursively enumerable) is the class of decision problems for which a 'yes' answer can be verified by a Turing machine in a finite amount of time. (If the answer is 'no,' on the other hand, the machine might never halt.)

Equivalently, RE is the class of decision problems for which a Turing machine can list all the 'yes' instances, one by one (this is what 'enumerable' means).

For class of the 'no' answers, see Co-RE.

Each member of RE is a recursively enumerable set.

[edit] Relations to other classes

RE is known to be strictly greater than R, and strictly nonequal to Co-RE. We have that

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

[edit] External links

v • d • e
Important complexity classes (more)
P • NP • co-NP • NP-C • co-NP-C • NP-hard • UP • #P • #P-C • L • NL • NC • P-C • PSPACE • PSPACE-C • EXPTIME • NEXPTIME • EXPSPACE • 2-EXPTIME • PR • RE • Co-RE • RE-C • Co-RE-C • R • BQP • BPP • RP • ZPP • PCP • IP • PH
Languages