Em relação às classes de complexidade de problemas...

Com base no mesmo assunto

Q251496

Ano: 2011 Banca: Marinha Órgão: Quadro Complementar Prova: Marinha - 2011 - Quadro Complementar - Segundo-Tenente - Engenharia de Computação |

Q251496 Algoritmos e Estrutura de Dados

Em relação às classes de complexidade de problemas, assinale a opção correta.

A classe de problemas em P consiste nos problemas que dado um "certificado" de uma solução, é possível verificar se a solução é correta em tempo polinomial no tamanho da entrada.

A classe de problemas NP consiste nos problemas que não pertencem a classe P, e por isso são problemas não "verificáveis" em tempo polinomial.

A busca binária é um problema em NP-completo, dependendo do tamanho da entrada.

Um problema que está em P não estará em NP, exceto problemas NP-completos, os quais não foram demonstrados pela ciência.

Dado que exista um problema NP-completo com solução em tempo polinomial, então todos os problemas em NP terão soluções em tempo polinomial.

Incorreta. Gabarito oficial da banca:

Salve essa questão em um caderno para revisar depois. Adicionar a um caderno

teste

Parabéns! Você acertou!

Mantenha o ritmo! Salve no caderno para revisar depois. Adicionar a um caderno

teste

🚀 Mais performance?

🚀 Mais performance?

Em relação às classes de complexidade de problemas...

Questões de assuntos semelhantes

Provas relacionadas