En teoría de la computación y teoría de la complejidad computacional, una reducción es una transformación de un problema a otro problema. Dependiendo de la transformación usada, la reducción se puede utilizar para definir clases de complejidad en un conjunto de problemas.
Intuitivamente, un problema 
  
    
      
        A
      
    
    {\displaystyle A}
   es reducible a un problema 
  
    
      
        B
      
    
    {\displaystyle B}
   si las soluciones de 
  
    
      
        B
      
    
    {\displaystyle B}
   existen y dan una solución para 
  
    
      
        A
      
    
    {\displaystyle A}
   siempre que 
  
    
      
        A
      
    
    {\displaystyle A}
   tenga solución.
Así, resolver 
  
    
      
        A
      
    
    {\displaystyle A}
   no puede ser más difícil que resolver 
  
    
      
        B
      
    
    {\displaystyle B}
  .
Normalmente, esto se expresa de la forma 
  
    
      
        A
        ≤
        B
      
    
    {\displaystyle A\leq B}
  , y se añade un subíndice en 
  
    
      
        ≤
      
    
    {\displaystyle \leq }
   para indicar el tipo de reducción utilizada.
Por ejemplo, se usa la letra 
  
    
      
        p
      
    
    {\displaystyle p}
   como subíndice para indicar que la reducción puede realizarse en tiempo polinomial: 
  
    
      
        A
        
          ≤
          
            p
          
        
        B
      
    
    {\displaystyle A\leq _{p}B}
  .