[grafos] fenômeno interessante?!?

[Jose Coelho de Pina <coelho@ime.usp.br>]

Salve,

A questão 3 da prova me fez refletir sobre um fenômeno que me
parece interessante.

(1) Computar distâncias a partir de um vértice em uma grafo
    com comprimentos arbitrários nos arcos gasta
    (essencialmente) tempo O(nm).  O Algoritmo de
    Bellman-Ford-Moore faz o serviço.
 
(2) Verificar se uma dada numeração dos vértices corresponde
    as distâncias a partir de um dado vértice gasta tempo
    linear, isto é, O(n+m).

A primeira vista parece que para resolver (2) é necessário
resolver (1), o que não é verdade. Nesse caso vemos que

    verificar se um candidato a solução é de fato uma 
    solução é mais `fácil' que encontrar uma solução. 

Esse fenômeno ocorre, de uma maneira muito mais gritante, em
outros problemas na natureza. Considere, por exemplo, o par
de problemas (3) e (4) abaixo.

(3) Encontrar, caso exista, um circuito hamiltoniano em um
    grafo. (Um circuito é hamiltoniano se ele `passa'
    _exatamente_ um vez em cada vértice do grafo).

(4) Verificar se um dado circuito é hamiltoniano.


O problema (4) pode ser resolvido em tempo linear.
Entretanto, a melhor solução que se conhece para (3) consome
tempo _exponencial_ (isso é tempo prá cachorro). Pior que
isto, há muita gente que acredita que _não existe_ um
algoritmo para (3) que consome uma quantidade de tempo
polinomial, mesmo se for  um polinômio da forma "n+m elevado a
1167".
   
Interessante, não?!? Existem problemas para os quais sabemos
verificar rapidamente se um candidato a solução é de fato
solução, apesar de não sabermos encontrar uma solução sem
para isto gastarmos uma quantidade de tempo imoral...
Intrigante, não?!?

té +,
coelho