redução

Em teoria da computação e complexidade, uma redução é uma transformação de um problema em outro. Dependendo da transformação utilizada, isto pode ser usado para definir classes de complexidade em um conjunto de problemas.Intuitivamente, o problema A é redutível ao problema B se existe uma maneira de transformar uma solução para B numa solução para A sempre que A tem solução. Assim, solucionar A não pode ser mais difícil que solucionar B. Escrevemos A ≤mB, geralmente com um símbolo subscrito no ≤ para indicar o tipo de redução que foi usada (m: redução por mapeamento; P: redução polinomial).