Seu próximo nível começa aqui
Seu desenvolvimento não pode ter limites. Garanta sua Assinatura Ilimitada e libere uma preparação completa com os melhores professores do Brasil.
Na computação, várias disciplinas aplicam conceitos...
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.