Problemas NP Completo

26/06/14

Problemas NP-Completo

Problemas NP-Completo
Introdução
Introduziremos no decorrer desta exposição, uma idéia do que seja um problema NPCompleto, de um problema NP-Árduo, definiremos o Teorema de Cook, demonstrando-o de forma abstrata, e descreveremos o que seja basicamente um problema SAT, além da idéia de algoritmos não-determinísticos.
Antes de todos estes conceitos, é importante que se ressalte que um problema P é dito tratável se ele possui um algoritmo de complexidade polinomial para resolvê-lo, e intratável em caso contrário.

Redução do tempo polinomial
Problemas de Decisão são aqueles que podem ser respondidos com sim ou não. Esta definição simplifica bastante todo o restante da teoria. Muitos problemas podem ser facilmente convertidos em problemas de decisão. Por exemplo, ao invés de procurar pelo tamanho máximo em um dado gráfico, questiona-se a existência de um valor > k.
Resolvendo-se o problema de decisão, pode-se resolver o problema original.
Um problema de decisão pode ser visto como um problema de reconhecimento de linguagem. Considere U come sendo o conjunto de todas as possíveis entradas para um problema de decisão. Considere L Í U como sendo o conjunto de todas as entradas cuja a resposta é sim. Nós chamaremos L de linguagem correspondente ao problema.
Partiremos agora para a definição de redução do tempo polinomial.
Definição: Considere L1 e L2 como sendo duas linguagens pertencentes a U1 e U2 .
Diremos que L1 é redutível polinomialmente a L2 se existe um algoritmo de tempo polinomial que converte cada entrada u1Î U1 a outra entrada u`2Î U2 tal que u1Î U1 se e somente se u2Î L2 .
O algoritmo mencionado na definição converte um problema em outro. Se temos um algoritmo para L2 , então podemos compor dois algoritmos para produzir um algoritmo para L1 . Denote o algoritmo de conversão por AC, e denote o algoritmo para L2 por
AL2 . Dada uma entrada arbitrária u1Î U1 nós podemos usar AC para converter u1 a uma entrada u2Î U2 ;Então usaremos