RE-complete

RE-complete is the set of decision problems that are complete for the complexity class RE consisting of all recursively enumerable problems. 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.
# [Myhill 1955] [Myhill, J. "Creative sets," Z. Math. Logik Grundlag. Math., v. 1, pp. 97–108.] 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.]
#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.
#The Domino Problem for Wang tiles.
#The validity problem for first-order logic.
#Determining if a Diophantine equation has any integer solutions.

References

ee also

List of undecidable problems