O conceito de redutibilidade na teoria da computação refere-se à: a. Habilidade de reduzir a complexidade de um problema de NP para um problema de...
O conceito de redutibilidade na teoria da computação refere-se à:
a. Habilidade de reduzir a complexidade de um problema de NP para um problema de P.
b. Capacidade de tornar um problema indecidível em um problema decidível.
c. Transformação de um problema em outro de tal forma que a solução do segundo problema possa ser usada para resolver o primeiro.
d. Técnica de otimização de algoritmos para torná-los mais eficientes.
e. Ideia de transformar um problema em outro problema de maior complexidade.
a. Habilidade de reduzir a complexidade de um problema de NP para um problema de P.
b. Capacidade de tornar um problema indecidível em um problema decidível.
c. Transformação de um problema em outro de tal forma que a solução do segundo problema possa ser usada para resolver o primeiro.
d. Técnica de otimização de algoritmos para torná-los mais eficientes.
e. Ideia de transformar um problema em outro problema de maior complexidade.
💡 1 Resposta
Ed 
O conceito de redutibilidade na teoria da computação refere-se à alternativa c: Transformação de um problema em outro de tal forma que a solução do segundo problema possa ser usada para resolver o primeiro. A redutibilidade é uma técnica importante para provar a complexidade de um problema, mostrando que um problema conhecido é pelo menos tão difícil quanto o problema em questã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
6 pág.
7 pág.
Compartilhar