Please enable JavaScript.
Coggle requires JavaScript to display documents.
ANÁLISE DE TRATABILIDADE - Coggle Diagram
ANÁLISE DE TRATABILIDADE
Classes de complexidade
NP-DIFÍCIL
NP-COMPLETO
NP
=?
P
P está contido em NP
Exemplos de P
Ordenação de listas
Busca em listas
Operações aritmética
Maior divisor comum
Primalidade*
Algoritmo descoberto em 2002
Travessia de grafos
Checar ciclicidade e conectividade de grafos
Menor caminho entre vértices de um grafo
Árvore abrangente mínima
Problemas em NP são transformáveis em NP-Completo em tempo polinomial
Exemplos de NP fora de P e de NP Completo (cenário NP != P)
Fatoração de inteiros
Problemas de isomorfismo em grafos
Determinar vencedor em jogos de paridade
Exemplos de NP-Completo
Caixeiro-viajante
SAT
m-clique
m-coloração
Problema da mochila
Problema da partição
Soma em sub-conjuntos
Circuito Hamiltoniano
NP-Completo está contido em NP-Difícil
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
Algoritmos determinísticos: Resoluções clássicas que geram um mesmo resultado para um mesmo input
Quando é solução para um problema em tempo polinomial, o problema é P
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
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
Problemas de Decisão
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