MO417 - Questão para a prova oral

Número: 111

Enunciado:
Dadas as seguintes afirmações, assinale a alternativa correta.


I - A operação de redução é reflexiva, ou seja, se o problema A pode ser reduzido ao problema B, então o problema B pode ser reduzido ao problema A.
II - Todos os problemas verificáveis em tempo polinomial estão contidos na classe de problemas P.
III - Se o problema A ∈ NPC é reduzível em tempo polinomial ao problema B ∈ P, então P=NP.
  1. Apenas as afirmações I e II estão corretas.
  2. Apenas as afirmações I e III estão corretas.
  3. Apenas a afirmação III está correta.
  4. Todas as afirmações estão incorretas.
  5. NDA

Autor(a): Alisson Pontes