Please enable JavaScript.
Coggle requires JavaScript to display documents.
COMPUTABILITY AND COMPUTATIONAL COMPLEXITY - Coggle Diagram
COMPUTABILITY AND COMPUTATIONAL COMPLEXITY
Dizemos que um algoritmo resolve um problema em tempo polinomial se sua eficiência de tempo de pior caso pertence a O(p(n)) onde p(n) é um polinômio de tamanho de entrada n do problema.
Problemas que podem ser resolvidos em tempo polinomial são chamados de tratáveis, e
problemas que não podem ser resolvidos em tempo polinomial são chamados intratáveis.
Não podemos resolver instâncias arbitrárias de problemas intratáveis em um período de tempo razoável a menos que tais instâncias sejam muito pequenas.
Existem muito poucos algoritmos de tempo polinomial úteis com o grau de um polinômio maior que três.
Tanto a soma quanto a composição de dois polinômios são sempre polinômios também.
A escolha desta classe levou ao desenvolvimento de uma extensa teoria, chamada de complexidade computacional, que busca classificar os problemas de acordo com
sua dificuldade inerente.
E de acordo com essa teoria, a intratabilidade de um problema permanece a mesma para todos os principais modelos de computação e todos os modelos razoáveis e esquemas de codificação de entrada para o problema em consideração.
A classe P é uma classe de problemas de decisão que podem ser resolvidos em tempo polinomial por algoritmos (determinísticos). Essa classe de problemas é chamada polinomial.
Problemas de decisão: com respostas sim/não.
problemas de decisão que não podem ser resolvidos por nenhum algoritmo são chamados indecidíveis, em oposição a problemas decidíveis que podem ser resolvidos por um algoritmo.
Classe NP
Não determinístico: gerando uma solução candidata arbitrária.
Determinístico: verificando se é uma solução de fato.
Um algoritmo não determinístico resolve um problema de decisão se for capaz de encontrar uma solução pelo menos uma vez e poder verificar sua validade
Um algoritmo não determinístico é dito não determinístico
polinomial se a eficiência de tempo de seu estágio de verificação for polinomial.
Algoritmo não determinístico
Sim: se houver pelo menos uma forma de realizar não determinísticas salta para encontrar uma solução válida.
Não: caso contrário.
Linguagem de programação hipotética não determinística
Todos os comandos típicos de uma linguagem de programação além de um salto não determinístico.
a classe de problemas de decisão que podem ser resolvidos em tempo polinomial por algoritmos não determinísticos
Diz-se que um problema de decisão D é NP-completo se:
Pertence à classe NP.
Todo problema em NP é polinomialmente redutível a D.
Diz-se que um problema de decisão D1 é polinomialmente redutível a um
problema de decisão D2, se existe uma função t que transforma instâncias de D1 para instâncias de D2 tais que:
Para todas as instâncias i ∈ D1, a resposta de i é sim
se, e somente se, a resposta de t(i) ∈ D2 for sim
t é computável por um algoritmo de tempo polinomial.
Mostrando que um problema de decisão D é NP-completo:
1 D está em NP: uma solução candidata pode ser verificada em tempo polinomial.
2 Todo problema em NP é redutível a D em tempo polinomial.
Existem problemas: tratáveis e intratáveis, mas são decidíveis.
Existem problemas indecidíveis (não computáveis).