Questão 765651

Tecnologia da Informação · 2019

Questão

ID 765651

Disciplina: Tecnologia da Informação

Assuntos: Complexidade de Algoritmos (Big-O, P x NP)

Ano: 2019 Banca: EsFCEx - Escola de Formação Complementar do Exército Órgão: Exército Brasileiro

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.

Alternativa 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.
Alternativa 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.
Alternativa 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.
Alternativa 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.
Alternativa 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.

Estatísticas Cadernos

Questão 765651

Continue estudando na plataforma