Aula número 12 - 20/11/20000

Assunto:NP-Completeness

Júlia Barata







    Um problema será NP-Complete se respeitar duas condições:

1) O problema é NP;

    2) E também NP-Hard.

    Os algoritmos NP, são algoritmos que não se conseguem resolver num tempo polinomial.

    Possíveis exemplos da complexidade deste tipo de problemas:

              O(2^n),

              O(n!).

    Apesar de não terem solução em tempo polinomail, podem ser verificados em tempo polinomial. Esta classe contem os problemas P como um subconjunto. O termo NP não significa "não polinomial", mas sim "problemas não determinados em tempo polinomial".

    Os algoritmos P (tempo polnomial), são aqueles que se podem resolver num tempo polinomial. Exemplos da complexidade deste tipo de problemas:

              O(ln n),

              O(n^2).

    Os algoritmos P tomam este nome porque a sua complexidade pode ser melhorada.

    Por um problema ser NP-Hard, não significa que seja difícil de resolver. E convém sublinhar que um problema pode ser NP-Hard, sem pertencer à classe NP.

    Pode-se demonstrar melhor a relação entre estes conceitos pelo esquema que se segue:







    Exemplos de problemas NP-Complete:

       1º exemplo: O problema da satisfação de um circuito:



(a)



(b)



    No circuito (a), conseguimos determinar facilmente a sua solução. Pois temos os valores de input (x1=1, x2=1, x3=0) que geram output igual a 1. E neste caso este circuito é satisfeito.

    No circuito (b), como não se tem o input do circuito, não sabemos tão facilmente qual a combinação que dara output 1. Assim podemos considerar este circuito "insatisfeito". Para se determinar qual o input que vai gerar output 1, teríamos que fazer todas as combinações possíveis dos vários input possíveis, o que vai levar um tempo superior ao polinomial.

    Logo o problema da satisfação do circuito é um problema NP-Complete.



       2º exemplo: O problema do caixeiro viajante:





    Este problema consiste no seguinte: o caixeiro viajante quer visitar todas as cidades, percorrendo a menor distância possível e voltar a casa sem passar em cidades que já visitou.

          Como encontrar a solução para este problema?

          1) Escrever todos os circuitos possíveis;
          2) Procurar quais os circuitos que percorrem todo o grafo, visitando todos os nós apenas uma única vez;
          3) Ver quais desses circuitos tem menor peso ;
          4) Escolher o circuito que melhor satisfaz o nosso pedido.

    Nota: A técnica da Aproximação (que não foi dada nas aulas), diz-nos que a distância encontrada não é duas vezes superior a solução óptima.

    Pode-se encontrar mais informação sobre este problema nos seguintes sites:





    Exercícios:

       1. Suponha que as instâncias de um certo problema são pares de cadeias de caracteres. O tamanho de uma instância é então da forma N+M, onde N é o comprimento da primeira cadeia do par e M é o comprimento da segunda cadeia. Suponha que a complexidade deste algoritmo é: O(N*2^M).
    Mostre que o algoritmo não é polinomial.

    Resolução:
        Este algoritmo não é polinomial porque tem um tempo polinomial (N), a multiplicar por um tempo exponencial (2^M).



        2. Mostre que a relação qualquer coisa <=p é transitiva na relação das linguagens. Isto é se L1<= pL2 e L2<=pL3, então L1<=pL3, (pág.938 do livro).

    Resolução:
        Considerando 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 pertencente U1 em outra entrada u2 pertencente U2, tal que u1 pertence U1 se e somente se u2 pertence a L2.

      O algoritmo descrito em cima converte um problema em outro. Se temos um algoritmo para L2, então podemos compor dois algoritmos para produzir um algoritmo para L1.

      Se chamarmos AC ao algoritmo de conversão, e renomearmos L2 para AL2. Dado um valor arbitrário u1 pertencente a U1 nós podemos usar AC para converter u1 como valor de u2 pertencente a U2. Então usaremos AL2 para determinar se u2 pertence a L2, o que nos vai levar a concluir seu1 pertence a L1.

      Isto pode-se resumir do seguinte modo:
      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.

      E ainda se: L1 é redutível polinomialmente a L2 e L2 é redutível polinomialmente a L3, então L1 é redutível polinomialmente a L3.





    Pode-se encontrar mais informação sobre os algortmos NP nos seguintes sites: