MO417 - QUESTÃO PARA A PROVA ORAL

Número: 2013-098

Enunciado: Assinale a alternativa correta, sabendo que NPC significa NP-completo:

1. A classe NP contém apenas linguagens, enquanto que a classe NPC contém apenas problemas de otimização.
2. Seja A uma linguagem da classe NP e B uma linguagem da classe NPC. Se conseguirmos provar que A não pode ser decidida em tempo polinomial, então garantiremos que B também não pode.
3. Seja A uma linguagem em NPC e B uma linguagem qualquer.  Se encontrarmos uma redução de tempo polinomial que transforma instâncias de A em instâncias de B, então provamos que B também está em NPC.
4. Seja P um problema de otimização.  Considere as linguagens:
   A = {<p,k> | p é uma instância de P com solução ≤ k}
   B = {<p,k> | p é uma instância de P com solução ≥ k}
   Então, A ∈ NPC implica em B ∈ NPC. 
5. N.D.A

Ideia original de: Danielle Furtado dos Santos Dias