RE (complexity)

RE (complexity)

In computability theory and computational complexity theory, 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. Informally, it means that if the answer is 'yes', then there is some procedure which takes finite time to determine this. On the other hand, if the answer is 'no', 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).

Similarly, co-RE is the set of all languages that are complements of a language in RE. In a sense, co-RE contains languages of which membership can be disproved in a finite amount of time, but proving membership might take forever.

Each member of RE is a recursively enumerable set and therefore a Diophantine set.