eri

MO417 - Questão para a prova oral

Número:

Enunciado:

I – Se um problema X pode ser reduzido a um outro problema Y, então, certamente, X é tão difícil quanto Y.

II – Seja X um problema tal que X ∈ Ω(n²). Se X pode ser reduzido a um outro problema Y, então, certamente, haverá um algoritmo A, com tempo de execução Ω(n²), para resolver Y.

III – Os problema de cobertura de vértices e caminho mais longo pertencem a classe NP-Completo.

IV – Se P = NP, então, para todo problema de decisão X, X ∈ NP-Completo.

De acordo com as afirmações acima, marque a alternativa correta:

a)      As afirmativas I e II estão corretas.

b)      As afirmativas II e III estão corretas.

c)      Apenas a afirmativa III está correta.

d)     As afirmativas III e IV estão corretas.

e)      N.D.A. 

Ideia original de:  Erick Aguiar Donato