Problemas NP-Completo

Introdução

Introduziremos no decorrer desta exposição, uma idéia do que seja um problema NP-Completo, 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 AL2 para determinar se u2 pertence a L2, isso nos dirá se u1 pertence a L1.Particularizando,temos os seguintes teoremas:

Teorema 1.1

Se L1 é redutível polinomialmente a L2 e existe um algoritmo de tempo polinomial para L2, então teremos um algoritmo de tempo polinomial para L1.

Teorema 1.2

Se L1 é redutível polinomialmente a L2 e L2 é redutível polinomialmente a L3, então L1 é redutível polinomialmente a L3.

A essência do método apresentado até o momento é procurar por algoritmos equivalentes quando um algoritmo eficiente não pode ser encontrado.

 


Não-determinismo e Teorema de Cook

Antes de definirmos o que vem a ser um algoritmo não determinístico, é importante definir o que vem a ser uma primitiva Nd-Choice. Como seu nome sugere, é utilizada para lidar com escolhas, sendo associada a um número fixo de escolhas, tal que, para cada escolha, o algoritmo segue um diferente caminho computacional. Dada uma entrada x, um algoritmo não-determinístico realiza passos determinísticos regulares intercalado com o uso de primitivas Nd-Choice, e , no final, ele decide se aceita ou não x.

Diremos que um algoritmo não-determinístico reconhece uma linguagem L se:

Dada uma entrada x, é possível converter cada Nd-Choice encontrado durante a execução do algoritmo, dentro de uma escolha real tal que o resultado do algoritmo será para aceitar x, se e somente se, xÎ L.

Algoritmos não-determinísticos são muito poderosos, mas seu poder é limitado. Nem todos os problemas podem ser resolvidos eficientemente por algoritmos não-determinísticos. Por exemplo, suponha que o problema é determinar se o "matching" máximo em um dado grafo é exatamente k. Podemos usar um algoritmo de "matching" não-determinístico para encontrar um "matching" de tamanho k, se ele existir, mas não podemos determinar facilmente(nem não-determinísticamente) que não existe um "matching" de tamanho maior.

A classe de problemas que possui algoritmos não-determinísticos cujo passo de reconhecimento pode ser realizado por um algoritmo polinomial do tamanho da entrada, é chamada de NP. Um questionamento ainda não respondido é o que diz respeito a qual tipo de algoritmo é mais eficiente, não-determinísticos ou determinísticos. Um caminho para provar que os algoritmos não-determinísticos são mais eficientes que os determinísticos é mostrar que um problema NP não está em P. Ninguém foi capaz ainda. Entretanto para provar que as duas classes são iguais(P=NP), então taremos que mostrar que para todo problema pertencente a NP tem solução com um algoritmo determinístico de tempo polinomial. Também não foi provado(poucos acreditam na veracidade desta afirmação).

Definição: Um problema X é chamado um problema NP-Árduo se todo problema NP é redutível polinomialmente a X.

Definição: Um problema X é chamado NP-Completo se (1) X pertence a NP, e (2)X é NP-Árduo.

Cook provou que existem problemas NP-Completo: em particular, ele exibiu um certo problema que descreveremos brevemente. Uma vez encontrado um problema NP-Completo, provaremos que outros problemas também são NP-Completo. Para isso definiremos o lema a seguir.

Lema

Um problema X é NP-Completo, se (1) X pertence a NP, e (2) Y é redutível polinomialmente a X, para algum problema Y que é NP-Completo.

Demonstracão: Pela condição 2 na definição de NP-Completo, cada problema em NP é redutível polinomialmente a Y. Mas desde que Y é redutível polinomialmente a X e redutibilidade é uma relação transitiva, cada problema em NP é redutível polinomialmente a X. De posse disto e da condição 1, prova-se que X é NP-Completo.

 


O Problema SAT

Dadas as variáveis booleanas x1,x2,x3 de um problema W e x1, x2, x3 seus complementos, ao conjunto de todas as variáveis de W e seus complementos dá-se o nome de literais. Denote-se por V e L as operações binárias, disjunção (ou) e conjunção (e). Define-se uma cláusula como sendo uma disjunção de literais. Uma expressão booleana possui literais como operandos e as conjunções e disjunções como operadores. Uma expressão booleana S estará na Forma Normal Conjuntiva (FNC) quando for uma conjunção de cláusulas, ou seja, produtos de varias somas. Ex.: S=(x1 V x2) L (x3 V x1 V x2) L (x2 V x3)

Uma expressão booleana é satisfatível quando o valor da expressão é verdadeira para determinados valores das variáveis que a compõem.

O problema SAT consiste em verificar se uma expressão booleana na FNC é satisfatível.

 


Teorema de Cook

O problema SAT é NP-Completo.

Demonstração: O Problema SAT é NP porque nós podemos supor uma associação verdadeira e checar que ela satisfaz a expressão em tempo polinomial. Para provar que SAT é NP-Árduo utiliza-se a Máquina de Turing , provando desta forma que SAT é NP-Completo.