MO417 - Questão para a prova oral

Número: 108

Enunciado: Se um problema A pode ser reduzido a um outro problema B, e o custo da redução é menor que o custo de resolver A, e também menor que o custo de resolver B, então podemos dizer que:

1. A é mais fácil que B.
2. A é no máximo tão difícil quanto B.
3. B é um subproblema de A.
4. Entradas válidas de A também são entradas válidas de B.
5. NDA.

Autor(a): Rodrigo Tripodi Calumby