Reduction (computability theory)

<p>In <a href="/facts/Computability_theory/cqDfXwdf">computability theory</a>, many reducibility relations (also called reductions, reducibilities, and notions of reducibility) are studied. They are motivated by the question: given sets 
  
    
      
        A
      
    
    {\displaystyle A}
  
 and 
  
    
      
        B
      
    
    {\displaystyle B}
  
 of natural numbers, is it possible to effectively convert a method for deciding membership in 
  
    
      
        B
      
    
    {\displaystyle B}
  
 into a method for deciding membership in 
  
    
      
        A
      
    
    {\displaystyle A}
  
?  If the answer to this question is affirmative then 
  
    
      
        A
      
    
    {\displaystyle A}
  
 is said to be reducible to 
  
    
      
        B
      
    
    {\displaystyle B}
  
. 
</p><p>The study of reducibility notions is motivated by the study of <a href="/facts/Decision_problems/cQNWjbdE">decision problems</a>. For many notions of reducibility, if any <a href="/facts/Computable_set/rsnT9cLn">noncomputable</a> set is reducible to a set 
  
    
      
        A
      
    
    {\displaystyle A}
  
 then 
  
    
      
        A
      
    
    {\displaystyle A}
  
 must also be noncomputable.  This gives a powerful technique for proving that many sets are noncomputable.
</p>

Reduction (computability theory) open-in-new

Reduction (computability theory)