Please enable JavaScript.
Coggle requires JavaScript to display documents.
Limits to Computation - Coggle Diagram
Limits to Computation
TEORIA NP-COMPLETUDE
Máquina não-determinística
"Adivinha" solução correta
Verifica em tempo polinomial
Teste de todas as soluções em paralelo
Classes de problemas
P: Polinomial em máquina determinística
NP: Polinomial em máquina não-determinística
NP-difícil: Qualquer problema NP reduz a X
NP-completo: NP ∩ NP-difícil
Exemplos NP-completos
TRAVELING SALESMAN (versão decisão)
K-CLIQUE
SATISFIABILITY (SAT)
Provas de NP-completude
SAT como primeiro problema (Cook)
3-SAT reduzido de SAT
K-CLIQUE reduzido de SAT
Estratégias para lidar com NP-completos
Instâncias pequenas
Casos especiais (grafos bipartidos, 2-SAT)
Algoritmos pseudo-polinomiais (Knapsack)
Backtracking e Branch-and-Bound
Aproximação com garantias (BIN PACKING)
Questão P = NP?
Se P = NP: Todos NP têm solução polinomial
Problema aberto mais importante da ciência da computação
REDUÇÃO
Conceito: Resolver um problema usando outro
Processo em 3 etapas
Transformar entrada do problema A para B
Aplicar algoritmo do problema B
Transformar saída de B para A
Estabelece limites
Limite superior: A ≤ B
Limite inferior: B ≥ A
Exemplos
PAIRING reduzido a SORTING
Multiplicação via formula de quadrados
Matrizes simétricas para matrizes gerais
PROBLEMAS DIFÍCEIS
Definição: Algoritmos com tempo exponencial
Tempo polinomial vs exponencial
Polinomial: Θ(n^k) - viável
Exponencial: Ω(c^n) - inviável
Computador 2x mais rápido
Polinomial: problema maior
Exponencial: apenas +1 no tamanho
Torres de Hanói: Θ(2^n)
Diferenças qualitativas
Polinômios fechados sob composição
Todos os computadores polinomialmente relacionados
PROBLEMAS IMPOSSÍVEIS
Contabilidade vs Incontabilidade
Programas: Contáveis (strings finitas)
Funções: Incontáveis (diagonalização)
Conclusão: Nem toda função tem programa
Problema da Parada
Entrada: Programa P e entrada I
Saída: P para em I?
Prova por contradição (função contrary)
Consequência: Impossível de resolver
Outros problemas impossíveis
Programa para em entrada vazia?
Existe entrada que faz programa parar?
Programa computa função específica?
Dois programas computam mesma função?
Linha específica é executada?
Programa contém vírus?
Exemplos práticos
Sequência de Collatz (problema em aberto)
Verificação de correção de programas
Detecção de vírus (heurísticas funcionam)