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.

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.

Questões Programação

Segundo Thomas Cormen, cientistas da computação ge...

Responda: Segundo Thomas Cormen, cientistas da computação geralmente consideram problemas resolvíveis por algoritmos de tempo polinomial como “tratáveis”, o que quer dize...

1Q711723 | Programação, Oficial Infomática, EsFCEX, Exército Brasileiro, 2019

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.