Na computação, várias disciplinas aplicam conceitos matemáticos avançados para resolver...

Q895491 | Algoritmos e Estrutura de Dados, Complexidade de Algoritmos, Gestor de Tecnologia da Informação, Câmara de Alto Paraíso RO, Gama Consult, 2024

Na computação, várias disciplinas aplicam conceitos matemáticos avançados para resolver problemas complexos. Uma dessas disciplinas é a Teoria da Complexidade Computacional, que estuda a eficiência dos algoritmos e a dificuldade dos problemas. Considere os conceitos de classes de complexidade, problemas NP-completos e algoritmos aproximados. Qual das seguintes afirmações sobre essas disciplinas é a mais correta?

a) Todo problema na classe NP pode ser resolvido em tempo polinomial por um algoritmo determinístico.
b) Um problema NP-completo é aquele para o qual não existe nenhum algoritmo de aproximação eficiente conhecido.
c) Se um problema NP-completo puder ser resolvido em tempo polinomial, todos os problemas em NP também poderão ser resolvidos em tempo polinomial.
d) Algoritmos aproximados garantem sempre a solução exata de problemas NP-difíceis em tempo polinomial.