Please enable JavaScript.
Coggle requires JavaScript to display documents.
COMPUTABILITY AND COMPUTATIONAL COMPLEXITY - Coggle Diagram
COMPUTABILITY AND COMPUTATIONAL COMPLEXITY
Computabilidade
A capacidade de um problema ser resolvido por um algoritmo
Tese de Church-Turing
Qualquer problema solucionável por um algoritmo é solucionável por uma máquina de Turing
Problemas indecidíveis:
Problemas para os quais não existe um algoritmo que sempre termine e dê a resposta correta, como o "Problema da Parada"
Problemas decidíveis
Problemas para os quais existe um algoritmo que sempre termina e dá a resposta correta.
Complexidade computacional
Classes de Complexidade
NP
Problemas verificáveis em tempo polinomial.
NP-COMPLETO
Problemas mais difíceis dentro de NP.
P
Problemas solucionáveis em tempo polinomial.
NP-DIFÍCIL
Problemas tão difíceis quanto os NP-completos.
Mede o tempo e espaço necessários para resolver um problema
Reduções
Mapeamento de um problema para outro para provar complexidade.
Redução NP-completo:
Transformação que prova a dificuldade NP-completa.
Redução polinomial:
Transformação eficiente de um problema em outro.