redução
Sign in to savetransformation of one computational problem to another, used to show that the second problem is as difficult as the first
In the Vinony graph
Vinony's link graph records 94 inbound references to redução, and connects out to time complexity, polynomial-time reduction and International Standard Book Number.
It is catalogued under the topic Reduction (complexity).
Vinony links it to 19 Wikipedia language editions.
Wikidata facts
Show 3 more facts
- facet of
- problem solving
- Stack Exchange tag
- cstheory.stackexchange.com/tags/reductions
- maintained by WikiProject
- WikiProject Mathematics
Sources (1)
via Wikidata · CC0
Article · Português
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).
Abstract from DBpedia / Wikipedia · CC BY-SA