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.

 

 

Algoritmo de Fleury

 

função Fleury(G = (V,E): grafo) : caminho

G' := G     { G' = (V', E')}
v₀ := um vértice de G'
C := [v₀] {Inicialmente, o circuito contém só v₀}
Enquanto E' não vazio

v_i := último vértice de C
Se v_i tem só uma aresta incidente;

a_i := a aresta incidente a v_i em G'

Senão

a_i := uma aresta incidente a v_i em G' e que não é uma ponte

Retirar a aresta a_i do grafo G'
Acrescentar a_i no final de C
v_j := vértice ligado a v_i por a_i
Acrescentar v_j no final de C

Retornar C

Para entender como funciona o algoritmo de Fleury, considere o grafo da figura 4a. Suponhamos que o algoritmo começa com o vértice 6. Ele pode escolher uma das arestas h, d, e ou i. Supondo que ele escolhe d, ele se encontra depois no vértice 2, onde ele é obrigado a seguir pela ponte que liga com o vértice 5. Isso é ilustrado na figura 4b. Nesse momento, ele pode escolher entre b, g o h. O último é descartado por ser uma ponte. Então sobram somente b e g. Supondo que b é selecionado, ele chega ao vértice 1, como ilustrado em 4. Nas três próximas etapas, ele não tem escolha. Chegando ao vértice 6, de novo ele tem mais du uma opção. Em mais três etapas, ele volta à origem, o que completa o circuito euleriano.

Agora, podemos resolver facilmente o problema das pontes de Königsberg. Simplesmente temos que ver se grafo utilizado para representar o problema é um grafo euleriano. Mas como nem todos os vértices desse grafo possuem grau par, ele não é um grafo euleriano. Então, é impossível atravessar todas as pontes uma vez só e voltar no lugar da partida.