MO417 - Questão para a prova oral

Número: 166

Enunciado:
Dadas as seguintes afirmações sobre o tema NP-Completude (P, NP e NPC(NP-Completo)) e reduções entre problemas (linguagens), assinale a alternativa correta:
I - Se a linguagem L₁ pertence a NPC e L₁ reduz-se a L₂, então se L₂ pertence a P podemos afirmar que P=NP.
II - Se a linguagem L₁ pertence a P, então ela pode ser verificada em tempo polinomial.
III - Se P=NP, então existe algoritmo polinomial para decidir qualquer linguagem.

1. Todas as afirmações estão corretas
2. Apenas as afirmações II e III estão corretas
3. Apenas as afirmações I e III estão corretas
4. Apenas as afirmações I e II estão corretas
5. NDA

Autor(a): Jefferson Luiz Moisés da Silveira RA:089044