MO417 - Questão para a prova oral

Número: 107

Enunciado:
Considerando as classes de complexidade P, NP e NP-completo, bem como as reduções entre os problemas de decisão A, B e C, é possível afirmar que:

I. Para quaisquer dois problemas A e B pertencentes à classe NP, 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

Autor(a): Priscila Tiemi Maeda Saito