Questão 3136039

• Banca: Exército
• Órgão: EsFCEx
• Ano: 2019
• Provas: Exército - 2019 - EsFCEx - Oficial - Informática
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

Segundo Thomas Cormen, cientistas da computação geralmente consideram problemas resolvíveis por algoritmos de tempo polinomial como “tratáveis”, o que quer dizer “fácil de lidar”. Se existir um algoritmo de tempo polinomial para um problema, então se diz que esse problema está na classe P. A respeito dos algoritmos de redução em tempo polinomial, assinale a alternativa correta.

• A. Se o problema X é NP-completo e pode-se reduzi-lo ao problema Y em tempo polinomial, então o problema Y se torna da classe P.
• B. Se o problema X é NP-difícil e pode-se reduzi-lo ao problema Y em tempo polinomial, então o problema Y pode ser NP-difícil.
• C. Se o problema X é NP-difícil e pode-se reduzi-lo ao problema Y em tempo polinomial, então o problema Y depende da ordem de complexidade.
• D. Se o problema X é NP-difícil e pode-se reduzi-lo ao problema Y em tempo polinomial, então o problema Y é NP-difícil também.
• E. Se o problema X é NP-difícil e pode-se reduzi-lo ao problema Y em tempo polinomial, então o problema Y não é NP-difícil.

Gabarito: D

Comentários

• essa questão não extrapolou o edital não? alguém chegou a recorrer?

• Acredito que não extrapolou, pois faz parte do conteúdo cobrado:

  4. Técnicas de programação

  b. Estrutura de dados: vetores, matrizes, cadeia de caracteres, listas lineares, pilhas, filas,

  árvores, grafos, pesquisa de dados, classificação de dados, estruturas e tipos abstratos de dados,

  recursividade, eficiência e complexidade.

  Acredito que essa imagem explique a resposta:

  https://upload.wikimedia.org/wikipedia/commons/thumb/6/66/P_np_np-completo_np-hard.svg/450px-P_np_np-completo_np-hard.svg.png

  Se um problema NP pode ser resolvido em tempo polinomial, logo esse problema seria NP também, pois fazem parte do mesmo conjunto.

• nessa eu concordo com você Diego, estou lendo o livro do Cormen desde o começo do ano e realmente, no início do capítulo de complexidade eu já aprendi a resolução dessa questão, e esse livro está na bibliografia do concurso, tudo bem que tá no fim do livro kkkk penúltimo capítulo, mas está lá, agora eu aprendi...boa sorte a todos nós!