Llegint llegint...
Cito el que he trobat en el llibre (mentre estudiava) "Fundamentos de Algoritmia" de l'editorial Pearson, pàgina 493 - 494, el tema de Introducció a la NP-Completitut:
"Considere como ejemplo el problema consistente en decidir si un grafo es hamiltoniano. Aun cuando se cree que este problmea es difícil, es verificable eficientemente: si el ser nos muestra un ciclo hamiltoniano, es sencillo verificar si es o no correcto. Por otra parte, nada de lo que nos muestre el ser -con la posible excepción de una escopeta- podrá convencernos de que el grafo es hamiltoniano si no lo es realmente."
"Considere como ejemplo el problema consistente en decidir si un grafo es hamiltoniano. Aun cuando se cree que este problmea es difícil, es verificable eficientemente: si el ser nos muestra un ciclo hamiltoniano, es sencillo verificar si es o no correcto. Por otra parte, nada de lo que nos muestre el ser -con la posible excepción de una escopeta- podrá convencernos de que el grafo es hamiltoniano si no lo es realmente."
Comentaris