Please enable JavaScript.
Coggle requires JavaScript to display documents.
Limits to Computation - Coggle Diagram
Limits to Computation
17.1 Reduções
Transformar um problema em outro
Usada para comparar complexidade
Exemplo: PAIRING → SORTING
Reduções mostram:
Limite superior (o quanto pode custar)
Limite inferior (o quanto deve custar)
17.2.1 NP-Completude
NP
Solução verificável em tempo polinomial
NP-hard
Qualquer problema de NP pode ser reduzido a ele
NP-completo
Está em NP e é NP-hard
Ex: TRAVELING SALESMAN, K-CLIQUE
Importância
Resolver um → resolve todos
17.2 Problemas Difíceis
Problemas com soluções exponenciais
Exemplo: Torre de Hanói (Θ(2ⁿ))
Diferença:
Polinomiais → viáveis
Exponenciais → impraticáveis
17.2.2 Provas de NP-Completude
Passos:
Mostrar que está em NP
Reduzir problema NP-completo conhecido
Ex: SAT, 3-SAT, VERTEX COVER, K-CLIQUE
17.3 Problemas Impossíveis
Incontabilidade
Existem mais funções que programas
Nem toda função é computável
Prova por diagonalização de Cantor
Halting Problem
Problema: decidir se um programa para
Prova por contradição usando função "contrary()"
Extensões do problema
Programa para toda entrada
Programa com entrada vazia
Dois programas são equivalentes
Linha de código é executada
Programa contém vírus
17.2.3 Lidando com NP-Completude
Estratégias:
Resolver instâncias pequenas
Focar em casos especiais (ex: grafos bipartidos)
Usar aproximações ou heurísticas