ANÁLISE DE TRATABILIDADE
Classes de complexidade
NP-DIFÍCIL
NP-COMPLETO
NP
=?
Problemas tratáveis
vs
Problemas não tratáveis
Tratáveis: solucionáveis por algoritmos de custo polinomial
Intratáveis: solucionáveis por algoritmos de custo exponencial
Algoritmos determinísticos vs
Algoritmos não determinísticos
Problemas de Decisão
P
P está contido em NP
Problemas em NP são transformáveis em NP-Completo em tempo polinomial
Algoritmos determinísticos: Resoluções clássicas que geram um mesmo resultado para um mesmo input
Algoritmos não determinísticos: Gera uma resposta aleatória e verifica se esta é uma solução para o problema
Quando é solução para um problema em tempo polinomial, o problema é NP
Quando é solução para um problema em tempo polinomial, o problema é P
Perguntas de sim ou não
Problemas complexos podem ser reduzidos a problemas de decisão
A versão reduzida a problema de decisão dos problemas complexos é que são analisadas na determinação de sua classe de complexidade
Linguagem hipotética de programação não-determinística
Capaz de realizar saltos não determinísticos (nd-jumps)
Geração de respostas aleatórias para o problema
Capaz de verificar se existe uma resposta possível para o problema que possa ser obtida pelos saltos
Resolveria problemas da classe NP em tempo polinomial
Exemplos de NP-Completo
Exemplos de NP fora de P e de NP Completo (cenário NP != P)
Exemplos de P
NP-Completo está contido em NP-Difícil
Caixeiro-viajante
SAT
m-clique
m-coloração
Problema da mochila
Problema da partição
Fatoração de inteiros
Problemas de isomorfismo em grafos
Determinar vencedor em jogos de paridade
Soma em sub-conjuntos
Ordenação de listas
Busca em listas
Circuito Hamiltoniano
Operações aritmética
Maior divisor comum
Primalidade*
Travessia de grafos
Checar ciclicidade e conectividade de grafos
Menor caminho entre vértices de um grafo
Árvore abrangente mínima
Algoritmo descoberto em 2002