Por que tenta-se reduzir os problemas NP, sempre que possível, para um problema P? a.Porque a complexidade de tempo polinomial é a melhor possível ...
Por que tenta-se reduzir os problemas NP, sempre que possível, para um problema P?
a.Porque a complexidade de tempo polinomial é a melhor possível para um algoritmo.
b.Porque a complexidade polinomial é considerada “razoável”, não sendo a melhor possível, mas também não sendo a pior.
c.Porque é conhecido que todos os algoritmos possuem pelo menos uma solução exponencial e tenta-se melhorar essa complexidade de tempo.
d.Porque é sabido que, mesmo que ainda não se tenha um algoritmo conhecido formalizado, sabe-se que todos os algoritmos podem ser resolvidos em tempo polinomial.
e.Porque deseja-se padronizar o tempo de execução dos diferentes algoritmos que são aplicados para problemas de natureza diversas.
💡 1 Resposta
Ed 
A alternativa correta é a letra A: "Porque a complexidade de tempo polinomial é a melhor possível para um algoritmo". Problemas NP são aqueles que não possuem solução conhecida em tempo polinomial, ou seja, a complexidade do algoritmo cresce exponencialmente com o tamanho da entrada. Já os problemas P são aqueles que possuem solução em tempo polinomial. Por isso, quando se consegue reduzir um problema NP para um problema P, significa que encontrou-se uma solução mais eficiente e rápida para o problema em questão. A complexidade de tempo polinomial é considerada a melhor possível para um algoritmo, pois cresce de forma mais lenta do que a complexidade exponencial, o que torna a solução mais viável em termos de tempo de execução.
Faça como milhares de estudantes: teste grátis o Passei Direto
Esse e outros conteúdos desbloqueados
16 milhões de materiais de várias disciplinas
Impressão de materiais
Agora você pode testar o
Passei Direto grátis
✏️ Responder
Para escrever sua resposta aqui, entre ou crie uma conta
Outros materiais
Perguntas relacionadas
Materiais relacionados
87 pág.
39 pág.
Compartilhar