Historicamente, a expressão algoritmo eficiente é associada aos algoritmos de complexidade polinomial. Diante disso, julgue as alternativas a segui...

A alternativa correta é a letra B. A afirmação "Tipo de problema computacional em que é necessário determinar a melhor solução possível entre todas as soluções viáveis por meio da força bruta é um problema que não pode ser resolvível em tempo polinomial" está correta. Esse tipo de problema é conhecido como NP-completo e não pode ser resolvido em tempo polinomial, ou seja, não é tratável ou fácil. Já a afirmação "O campo de complexidade computacional classifica problemas pelo grau de dificuldade em resolvê-los" está correta. A classificação de problemas em termos de complexidade é uma das principais áreas da teoria da computação. As outras alternativas não estão corretas, pois a afirmação "A. Resposta incorreta" e "B. Resposta incorreta" não apresentam justificativas ou explicações para a sua escolha.

Resposta correta.C. 

Se um algoritmo apresentar complexidade polinomial, ele é dito tratável ou resolvível em tempo polinomial, também conhecido como tratável ou fácil.

O campo de complexidade computacional classifica problemas pelo grau de dificuldade em resolvê-los. "Dificuldade", nesse sentido, é descrita em termos de esforço computacional necessário para o algoritmo mais eficiente para determinado problema. Em geral, designam-se os problemas resolvíveis em tempo polinomial como tratáveis, ou fáceis. Tipo de problema computacional em que é necessário determinar a melhor solução possível entre todas as soluções viáveis por meio da força bruta é um problema que não pode ser resolvível em tempo polinomial. Algoritmos não polinomiais (que não pertencem à classe P) podem levar séculos para serem executados, mesmo para entradas de tamanho reduzido.

CORRIGIDO PELO AVA