MO417 - Questão para a prova oral

Número: 2010-115

Enunciado: Dadas as seguintes afirmações, onde NPC significa NP-Completo, assinale a alternativa correta:

I. L ∈ NPC se para todo L' ∈ NP, L' ≤_p L.
II. L ≤_p L' se existe uma função f polinomial tal que x ∈ L se e somente se f(x) ∈ L'.
III. Se L" ≤_p L' e L'≤_p L, então L" ≤_p L.
IV. L’ ≤_p L para alguma L’ ∈ NPC, então L é NP-difícil.

1. Apenas uma afirmação está correta.
2. Apenas duas afirmações estão corretas.
3. Apenas três afirmações estão corretas.
4. Todas as afirmações estão corretas.
5. NDA

Ideia original de: Fábio Augusto Faria