RE (complexity) - RE-complete

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:

1. Halting problem: Whether a program given a finite input finishes running or will run forever.
2. 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.
3. John Myhill (1955) has proven that all creative sets are RE-complete.
4. The uniform word problem for groups or semigroups.
5. Deciding membership in a general unrestricted formal grammar.
6. The validity problem for first-order logic.
7. 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.
8. Determining if a Diophantine equation has any integer solutions.