RE (complexity)

<h2 id="equivalent-definition">Equivalent definition</h2>
<p>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 <a href="/facts/Recursively_enumerable_set/lpzr8jHn">recursively enumerable set</a> and therefore a <a href="/facts/Diophantine_set/ScKH6ne2">Diophantine set</a>.
</p><p>To show this is equivalent, note that if there is a machine 
  
    
      
        E
      
    
    {\displaystyle E}
  
 that enumerates all accepted inputs, another machine that takes in a string can run 
  
    
      
        E
      
    
    {\displaystyle E}
  
 and accept if the string is enumerated. Conversely, if a machine 
  
    
      
        M
      
    
    {\displaystyle M}
  
 accepts when an input is in a language, another machine can enumerate all strings in the language by interleaving simulations of 
  
    
      
        M
      
    
    {\displaystyle M}
  
 on every input and outputting strings that are accepted (there is an order of execution that will eventually get to every execution step because there are countably many ordered pairs of inputs and steps).
</p>
<h2 id="relations-to-other-classes">Relations to other classes</h2>
<p>The set of <a href="/facts/Recursive_language/4R0zBWJE">recursive languages</a> (<a href="/facts/R_(complexity)/RRLVW00j">R</a>) is a subset of both RE and co-RE.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> 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:
</p>

R
          
        
        =
        
          
            RE
          
        
        ∩
        
          
            co-RE
          
        
      
    
    {\displaystyle {\mbox{R}}={\mbox{RE}}\cap {\mbox{co-RE}}}
  
.
<p>Conversely, the set of languages that are neither RE nor co-RE is known as NRNC. These are the set of languages for which neither membership nor non-membership can be proven in a finite amount of time, and contain all other languages that are not in either RE or co-RE. That is:
</p>

NRNC
          
        
        =
        
          
            ALL
          
        
        −
        (
        
          
            RE
          
        
        ∪
        
          
            co-RE
          
        
        )
      
    
    {\displaystyle {\mbox{NRNC}}={\mbox{ALL}}-({\mbox{RE}}\cup {\mbox{co-RE}})}
  
.
<p>Not only are these problems undecidable, but neither they nor their complement are recursively enumerable.
</p><p>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 <a href="/facts/Quantum_entanglement/afzslwN0">entanglement</a>);<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> a revised, but not yet fully reviewed, proof was published in <i><a href="/facts/Communications_of_the_ACM/Ix1DvEAk">Communications of the ACM</a></i> in November 2021. The proof implies that the <a href="/facts/Connes_embedding_problem/UEnlnbS3">Connes embedding problem</a> and <a href="/facts/Tsirelson%2527s_problem/qlnD5GDC">Tsirelson's problem</a> are false.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a>
</p>
<h2 id="re-complete">RE-complete</h2>
<p>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 <a href="/facts/Many-one_reduction/YUKNlYPh">many-one reductions</a>.
</p><p>Examples of RE-complete problems:
</p>
<ol><li><a href="/facts/Halting_problem/Xz1bac40">Halting problem</a>: Whether a program given a finite input finishes running or will run forever.</li>
<li>By <a href="/facts/Rice%2527s_theorem/BhXVzM1z">Rice's theorem</a>, deciding membership in any nontrivial subset of the set of <a href="/facts/Computable_function/dzwBlLGn">recursive functions</a> is RE-hard. It will be complete whenever the set is recursively enumerable.</li>
<li><a href="/facts/John_Myhill/Ct2fUk07">John Myhill</a> (1955)<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> proved that all <a href="/facts/Creative_set/s7Mlbcx4">creative sets</a> are RE-complete.</li>
<li>The uniform <a href="/facts/Word_problem_(mathematics)/UJmKtmNF">word problem</a> for <a href="/facts/Group_(mathematics)/IQTYqINt">groups</a> or <a href="/facts/Semigroup/rgSdk2kt">semigroups</a>. (Indeed, the <a href="/facts/Word_problem_for_groups/eKBrkBPv">word problem for some individual groups</a> is RE-complete.)</li>
<li>Deciding membership in a general <a href="/facts/Unrestricted_grammar/u9mR49Dc">unrestricted</a> <a href="/facts/Formal_grammar/QLxaQNAz">formal grammar</a>. (Again, certain individual grammars have RE-complete membership problems.)</li>
<li>The <a href="/facts/Validity_(logic)/oMGkywGC">validity</a> problem for <a href="/facts/First-order_logic/lcISqWIg">first-order logic</a>.</li>
<li><a href="/facts/Post_correspondence_problem/YjHh66CM">Post correspondence problem</a>: 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.</li>
<li>Determining if a <a href="/facts/Diophantine_equation/mYaHp7oX">Diophantine equation</a> has any integer solutions.</li></ol>
<h2 id="co-re-complete">co-RE-complete</h2>
<p>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.
</p><p>Examples of co-RE-complete problems: 
</p>
<ol><li>The <a href="/facts/Domino_problem/639AJElj">domino problem</a> for <a href="/facts/Wang_tile/639AJElj">Wang tiles</a>.</li>
<li>The <a href="/facts/Satisfiability/NkmQFgHB">satisfiability</a> problem for <a href="/facts/First-order_logic/lcISqWIg">first-order logic</a>.</li></ol>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Knuth%25E2%2580%2593Bendix_completion_algorithm/cH66W8Rr">Knuth–Bendix completion algorithm</a></li>
<li><a href="/facts/List_of_undecidable_problems/SqtIWqsk">List of undecidable problems</a></li>
<li><a href="/facts/Polymorphic_recursion/DmIjtX8d">Polymorphic recursion</a></li>
<li><a href="/facts/Risch_algorithm/UcT2qrPl">Risch algorithm</a></li>
<li><a href="/facts/Decidability_(logic)/17SHPMo0">Semidecidability</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Complexity Zoo: Class RE <a href="/wiki/Complexity_Zoo" target="_blank">/wiki/Complexity_Zoo</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>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. <a href="https://archive.org/details/logicalgorithmsw0000korf" target="_blank">https://archive.org/details/logicalgorithmsw0000korf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Complexity Zoo: Class co-RE <a href="/wiki/Complexity_Zoo" target="_blank">/wiki/Complexity_Zoo</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Ji, Zhengfeng; Natarajan, Anand; Vidick, Thomas; Wright, John; Yuen, Henry (2020). "MIP*=RE". arXiv:2001.04383 [quant-ph]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Ji, Zhengfeng; Natarajan, Anand; Vidick, Thomas; Wright, John; Yuen, Henry (November 2021). "MIP* = RE". Communications of the ACM. 64 (11): 131–138. doi:10.1145/3485628. S2CID 210165045. <a href="https://doi.org/10.1145%2F3485628" target="_blank">https://doi.org/10.1145%2F3485628</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>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. <a href="/wiki/John_Myhill" target="_blank">/wiki/John_Myhill</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
</ol>

RE (complexity) open-in-new

RE (complexity)