Redução (complexidade)
De Wikipedia, a enciclopédia encyclopedia
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).
Este artigo ou secção contém uma lista de referências no fim do texto, mas as suas fontes não são claras porque não são citadas no corpo do artigo, o que compromete a confiabilidade das informações. (Agosto de 2011) |