Please enable JavaScript.
Coggle requires JavaScript to display documents.
Limites da Computação - Coggle Diagram
Limites da Computação
Classificação de problemas
Tratável
Existe solução em tempo polinomial EX: O(n logn)
Intratável
Existe solução em tempo exponencial ou maior EX: O(2^n)
Não-solucionável
Nenhum algoritmo pode resolver para qualquer entrada
Ferramentas e estratégias
Reduções
Técnica pra provar limites de dificuldade, transformando um problema em outro
Estratégias práticas
Backtracking, algoritmos de aproximação, heurísticas
Teoria da completude
P vs NP
P
Problemas de decisão resolvíveis em tempo polinomial por algoritmos determinísticos
NP
Problemas de decisão de solução que podem ser verificadas em tempo polinomial
NP-Completo: os problemas mais dificeis em NP
Problemas impossíveis
Problemas não solucionáveis
Problema da parada
é possivel criar um programa que determina se um programa arbitrário P para com uma entrada I?
Não. Isso é um problema não-solucionável, provado por contradição