Questão 2876677

• Banca: FCM
• Órgão: IFN-MG
• Ano: 2018
• Provas: FCM - 2018 - IFN-MG - Ciências da Computação: Teoria da Computação
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

Sobre uma importante classe de complexidade, a classe dos problemas NP-completos, NÃO se pode afirmar que

• A. CIRCUITO HAMILTONIANO é um problema NP-completo.
• B. COBERTURA POR VÉRTICES é um problema NP-completo.
• C. SATISFATIBILIDADE é um problema NP-completo.
• D. 2SAT é um problema NP-completo.
• E. CLIQUE é um problema NP-completo.

Gabarito: D

Comentários

• Gabarito D

  A lista abaixo contém alguns dos problemas bem conhecidos como NP-completo quando expressados como problemas decisórios:

  Problema de satisfatibilidade booleana (SAT)

  Jogo do 15

  Problema da mochila (Knapsack)

  Tetris

  Problema do ciclo hamiltoniano

  Problema de roteamento de veículos

  Problema do caixeiro viajante

  Problema da Torre de Hanoi

  Problema do isomorfismo de subgrafos

  Problema da soma de subconjuntos

  Problema do clique

  Problema de cobertura de vértices

  Problema de conjuntos independentes

  Vamos na fé !

  "Retroceder Nunca Render-se Jamais !"

  Força e Fé !

  Fortuna Audaces Sequitur !