Please enable JavaScript.
Coggle requires JavaScript to display documents.
Limits to Computation, The Theory of NP-Completeness, Reductions, NP…
-
-
Reductions
EX
Considerando um algoritmo de sorting, podemos resolver um problema de emparelhamento utilizando um algoritmo de sorting(ordenação)
Tecnicamente, dizemos que PAIRING se reduz a SORTING, porque SORTING é utilizado para resolver PAIRING.
-
-
Considere quaisquer dois problemas para os quais uma redução adequada de um para o outro possa ser encontrada.
O primeiro problema pega uma instância arbitrária de sua entrada, que chamaremos de I, e transforma I em uma solução, que chamaremos de SLN.
O segundo problema pega uma instância arbitrária de sua entrada, que chamaremos de I′, e transforma I′ em uma solução, que chamaremos de SLN′.
-
-
-
Podemos resolver um novo problema utilizando algoritmos antigos, e assim estabelecendo um limite superior para o novo problema. Ou provar um limite inferior para o custo de um novo problema, mostrando que ele poderia ser usado como uma solução para um problema antigo com um limite inferior conhecido
o processo de redução não nos fornece um algoritmo para resolver nenhum dos problemas por si só. Apenas nos dá um método para resolver o primeiro problema, visto que já temos uma solução para o segundo.
A redução nos dá uma maneira de compreender os limites de um problema em termos de outro. Especificamente, dadas transformações eficientes, o limite superior do primeiro problema é, no máximo, o limite superior do segundo. Por outro lado, o limite inferior do segundo problema é pelo menos o limite inferior do primeiro.
NP-Completeness Proofs
-
Para provar que os problemas são NP-completos, precisamos provar que apenas um problema H é NP-completo.
para mostrar que qualquer problema X é NP-difícil, basta reduzir H a X.
Ao fazer provas de NP-completude, é muito importante não fazer essa redução ao contrário!
Se reduzirmos o problema candidato X ao problema difícil conhecido H, isso significa que usamos H como uma etapa para resolver X.
-
quando reduzimos o problema difícil conhecido problema H para o problema candidato X, isso significa que estamos usando X como uma etapa para resolver H. E se sabemos que H é difícil, isso significa que X também deve ser difícil.
O primeiro passo crucial para fazer toda essa teoria decolar é encontrar um problema que seja NP-difícil.
A primeira prova de que um problema é NP-difícil (e porque está em NP, portanto NP completo) foi feita por Stephen Cook. O problema NP-completo do “avô(Turing)” que Cook usou é chamado SATISFIABILITY (ou SAT, para abreviar).
SAT
SIGN.
expressão booleana
inclui variáveis booleanas combinadas usando os operadores AND (·), OR (+) e NOT (para negar a variável booleana x escrevemos x).
-
DEF.
Input -> Uma expressão booleana E sobre as variáveis x1, x2, ... na forma normal conjuntiva.
Output -> SIM se houver uma atribuição às variáveis que torne E verdadeiro, NÃO caso contrário.
-
-
Uncountability
-
Antes de provar que o problema da parada(Halting Problem) é insolúvel, primeiro provamos que nem todas as funções podem ser implementadas como um programa de computador. Isto ocorre porque o número de programas é muito menor que o número de funções possíveis.
conjunto é considerado contável (ou contável infinito se for um conjunto com membros infinitos) se cada membro do conjunto puder ser atribuído exclusivamente a um número inteiro positivo.
conjunto é incontável (ou incontávelmente infinito) se não for possível atribuir a cada membro do conjunto um número inteiro positivo.
Hard Problems
o algoritmo mais conhecido para o problema é caro em seu tempo de execução. Definimos um algoritmo difícil como aquele que roda em tempo exponencial, ou seja, em Ω(c^n) para alguma constante c > 1.
-
-
-
-
-
Input -> Um gráfico direcionado G completo com distâncias positivas atribuídas a cada aresta do gráfico e um inteiro k.
-
Output -> SIM se houver um ciclo simples com distância total ≤ k contendo todos os vértices em G, e NÃO caso contrário
-
-