# 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.^{[1]} Informally, it means that if the answer to a problem instance is 'yes', then there is some procedure which takes finite time to determine this, and this procedure never falsely reports 'yes' when the true answer is 'no'. However, when the true answer is 'no', the procedure is not required to halt; it may go into an "infinite loop" for some 'no' cases. Such a procedure is sometimes called a **semi-algorithm**, to distinguish it from an algorithm, defined as a complete solution to a decision problem.^{[2]}

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).
Each member of **RE** is a recursively enumerable set and therefore a Diophantine set.

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.

## Relations to other classes[edit]

The set of recursive languages (**R**) is a subset of both **RE** and **co-RE**.^{[3]} In fact, it is the intersection of those two classes, because we can decide any problem for which there exists a recogniser and also a co-recogniser by simply interleaving them until one obtains a result. Therefore:

## RE-complete[edit]

**RE-complete** is the set of decision problems that are complete for **RE**. In a sense, these are the "hardest" recursively enumerable problems. All such problems are nonrecursive. Generally, no constraint is placed on the reductions used except that they must be many-one reductions.

Examples of RE-complete problems:

- Halting problem: Whether a program given a finite input finishes running or will run forever.
- By Rice's Theorem, deciding membership in any nontrivial subset of the set of recursive functions is
**RE**-hard. It will be complete whenever the set is recursively enumerable. - John Myhill (1955)
^{[4]}has proven that all creative sets are**RE**-complete. - The uniform word problem for groups or semigroups. [Indeed, the word problem for some individual groups is
**RE**-complete.] - Deciding membership in a general unrestricted formal grammar. [Again, certain individual grammars have
**RE**-complete membership problem.] - The validity problem for first-order logic.
- Post correspondence problem: Given a finite set of strings, determine if there is a string that can be factored into a composition of the strings (allowing repeats) in two different ways.
- Determining if a Diophantine equation has any integer solutions.

## co-RE-complete[edit]

**co-RE-complete** is the set of decision problems that are complete for **co-RE**. In a sense, these are the complements of the hardest recursively enumerable problems.

Examples of co-RE-complete problems:

- The Domino Problem for Wang tiles.
- The satisfiability problem for first-order logic

## See also[edit]

- Knuth–Bendix completion algorithm
- List of undecidable problems
- Polymorphic recursion
- Risch algorithm
- Semidecidability

## References[edit]

**^***Complexity Zoo*: Class RE**^**Korfhage, Robert R. (1966).*Logic and Algorithms, With Applications to the Computer and Information Sciences*. Wiley. p. 89.A method of solution will be called a

*semi-algorithm*for [a problem]*P*on [a device]*M*if the solution to*P*(if one exists) appears after the performance of finitely many steps. A semi-algorithm will be called an*algorithm*if, in addition, whenever the problem has no solution the method enables the device to determine this after a finite number of steps and halts.**^***Complexity Zoo*: Class co-RE**^**Myhill, John (1955), "Creative sets",*Zeitschrift für Mathematische Logik und Grundlagen der Mathematik*,**1**(2): 97–108, doi:10.1002/malq.19550010205, MR 0071379.