Analisar a complexidade de um problema computacional é definir o algoritmo que tem o melhor resultado em relação ao consumo de tempo em função do t...

Analisar a complexidade de um problema computacional é definir o algoritmo que tem o melhor resultado em relação ao consumo de tempo em função do tamanho da sua entrada, no pior caso, na resolução de determinado problema. Porém, ainda não foram descobertos os melhores algoritmos para resolver muitos problemas computacionais. Sobre a análise de complexidade de problemas NP, avalie as seguintes asserções e a relação proposta entre elas: I. A complexidade assintótica de ordem exponencial – O(cn) representa a melhor solução para os problemas da classe NP. PORQUE II. Os algoritmos de complexidade O(cn) são conhecidos como um problema não tratável se a solução para determinado problema contém o melhor resultado. A respeito dessas asserções, assin
I. A complexidade assintótica de ordem exponencial – O(cn) representa a melhor solução para os problemas da classe NP.
PORQUE
II. Os algoritmos de complexidade O(cn) são conhecidos como um problema não tratável se a solução para determinado problema contém o melhor resultado.
A. As duas asserções são proposições verdadeiras, e a segunda é uma justificativa correta da primeira.
B. As duas asserções são proposições verdadeiras, mas a segunda não é uma justificativa correta da primeira.
C. A primeira asserção é uma proposição verdadeira, e a segunda é uma proposição falsa.
D. A primeira asserção é uma proposição falsa, e a segunda é uma proposição verdadeira.
E. As duas asserções são proposições falsas.