[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