From Wikipedia, the free encyclopedia
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][1] 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.
[edit] References
- ^ Myhill, J. "Creative sets," Z. Math. Logik Grundlag. Math., v. 1, pp. 97–108.
[edit] See also
List of undecidable problems
