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 teoria da complexidade computacional, as classes P, NP e NP-completo descrevem relaç...
Na teoria da complexidade computacional, as classes P, NP e NP-completo descrevem relações entre problemas de decisão quanto ao tempo necessário para resolvê-los ou verificar suas soluções.
Com base nas definições formais e nas relações entre essas classes, assinale a alternativa correta.
A
Problemas classificados como NP-difíceis pertencem à classe NP e possuem algoritmos de verificação polinomial.
B
Problemas da classe NP são resolvidos por máquinas determinísticas em tempo polinomial.
C
Problemas da classe P correspondem exatamente aos problemas classificados como NP-completos.
D
Caso um problema NP-completo seja resolvido por um algoritmo determinístico em tempo polinomial, conclui-se que P = NP.
E
Problemas NP-completos não admitem algoritmos que determinem sua solução em tempo finito.