MO417 - Questão para a prova oral

Número: 2010-107

Enunciado: Considerando as classes de complexidade P, NP e NP-completo, bem como reduções entre os problemas de decisão A, B e C, é possível afirmar que: I. Para quaisquer dois problemas A e B, se A é da classe P e existe uma redução polinomial de B a A, então B também é da classe P
II. Se A é redutível polinomialmente a B e B é redutível polinomialmente a C, então A é redutível polinomialmente a C
III. Para quaisquer dois problemas A e B, se A é redutível polinomialmente a B, então B é redutível polinomialmente a A

1. Todas as alternativas são corretas
2. Apenas I e III são corretas
3. Apenas II e III são corretas
4. Apenas III é incorreta
5. NDA

Ideia original de: Priscila Tiemi Maeda Saito