is: . Not only are these problems undecidable, but neither they nor their complement are recursively enumerable. In January of 2020, a preprint announced a proof that RE was equivalent to the class MIP* (the class where a classical verifier interacts with multiple all-powerful quantum provers who share entanglement); a revised, but not yet fully reviewed, proof was published in Communications of the ACM in November 2021. The proof implies that the Connes embedding problem and Tsirelson's problem are false. 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. 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. proved 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 problems.) The validity problem for first-order logic. Post correspondence problem: Given a list of pairs of strings, determine if there is a selection from these pairs (allowing repeats) such that the concatenation of the first items (of the pairs) is equal to the concatenation of the second items. Determining if a Diophantine equation has any integer solutions. co-RE-complete 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 Knuth–Bendix completion algorithm List of undecidable problems Polymorphic recursion Risch algorithm Semidecidability References Complexity classes Undecidable problems