RE (complexity)
From Wikipedia, the free encyclopedia
 |
This article does not cite any references or sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. (June 2009) |
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 and therefore a Diophantine set.
[edit] Relations to other classes
RE is known to be strictly greater than R, and strictly nonequal to Co-RE.[citation needed] We have that
[edit] External links
|
|||||
