Un hombre recibe una misión: encontrar a una persona con un tatuaje del Pato Donald estampado en el culo. Es un problema aparentemente difícil de resolver. En general puede tomar mucho tiempo y esfuerzo encontrar a alguien así pero, en contraposición, corroborar que el hombre cumplió su misión es sencillo: basta bajarle los pantalones al candidato.
Muchos problemas de búsqueda tienen la particularidad de que, aunque parezca difícil (en términos de tiempo) encontrar lo que se desea, verificar la validez de una solución es relativamente rápido. La pregunta es si de verdad son tan difíciles de resolver como aparentan ser. No es claro. De pronto siempre existe al fondo una manera rápida de buscar.
Por ejemplo, determinar si un número es primo parece un problema de este tipo. Requiere constatar la existencia (o no) de un divisor. Encontrar un divisor, al menos siguiendo la estrategia más obvia, tarda demasiado, pero verificar que es un divisor sólo requiere dividir y revisar el residuo (esta operación puede tomar tiempo, pero no demasiado en relación a la longitud de los números involucrados). Por muchos años se sospechó que el problema de decidir si un número era primo o no debería ser rápido de resolver, pero sólo hasta hace diez fue descubierto un procedimiento que lo hace de manera rápida, concluyente y sin condiciones en los números a evaluar.
Otros problemas no han tenido la misma suerte pero tampoco han tenido la suerte opuesta: no se ha podido demostrar que no existe una solución rápida. En otras palabras, no se sabe si existen problemas de búsqueda con verificación de solución rápida que sean esencialmente difíciles. A los problemas con verificación de solución rápida los llaman NP. A los problemas con solución rápida los llaman P. Otra manera de plantear la pregunta es sí todo problema NP es en realidad P o si definitivamente existen problemas NP que no son P.
Muchos algoritmos de encriptación de uso diario basan su solidez en problemas de búsqueda con verificación rápida de solución que por lo pronto parecen ser esencialmente difíciles de resolver, como la factorización de números enteros (en el caso del algoritmo RSA). Si se demostrara que todo problema NP es P, la seguridad de estos sistemas se derrumbaría (y probablemente con ella la civilización como la conocemos). La conjetura más popular, por ende, es que P≠NP. Ese es el verdadero sacramento de nuestra fe.
Cuando habla de tiempo, me confunde porque yo lo entiendo como un problema tecnológico y no algo más grave. Por ejemplo, le agregamos más máquinas al asunto o le ponemos un computador cuántico a la cosa.
ve la confusión? cuál es el limitante más grande?
Usualmente el tiempo se mide en el número de operaciones que ejecuta la máquina. Una solución es “rápida” (P) cuando ese número es acotado por una función polinómial en la longitud de la entrada. Detalles técnicos omitidos hay por todos lados. Pero la idea esencial es esa: no se sabe si existe un problema de búsqueda con verificación de solución rápida que sea esencialmente difícil de resolver (o sea, que no tenga una solución rápida.)
La pregunta es para computadores que modelan máquinas de Turing. Un hipotético computador cuántico funcional no entraría en esa categoría y por tanto tendría su propia intepretación independiente de P y NP. Por ejemplo se sabe que hay problemas (Turing-)NP con algoritmos cuánticos de solución que son P pero sin Turing-algoritmo de complejidad P conocido.
Verificar la solución del vendedor viajero no es fácil, de ninguna manera.
Es fácil: se van marcando los punticos para asegurarse de que pase por todos. Y se suman las distancias recorridas para comparar con la solución anterior.
No, no es fácil, el objetivo del problema del vendedor viajero es minimizar el costo. Encontrar lo que en Medellín llamamos “el optimo optimo”.
Ok: Depende de como se presente. Cuando se presenta como un problema de decisión (dados los costos de viaje y un presupuesto, encontrar un viaje que se ajuste al presupuesto) la verificación es sencilla. En ese sentido es NP.
Como lo describe usted, el problema es NP-hard, que es otra categoría más complicada y verificar la solución efectivamente no es tan sencillo. (Una gracia de los problemas NP-hard es que creo que si se logra demostrar que P=NP, los NP-hard también se vuelven sencillos de resolver.)
[...] (Feb. 28, 2012): See also Search and Destroy (in Spanish), by Javier Moreno.] 43.614000 -116.202000 Like this:LikeBe the first to like this [...]
[...] ? (See also this post (in Spanish) by Javier [...]
Es la primera vez que entiendo de qué se trata el meollo de P=NP. La definición de los libros de ciencia de la computación no me parece muy satisfactoria.
Me alegra. Es bastante burdo, pero la idea es esencialmente esa.
[...] (Feb. 28, 2012): See also Search and Destroy (in Spanish), by Javier Moreno.] 43.614000 -116.202000 Like this:LikeBe the first to like [...]
[...] ? (See also this post (in Spanish) by Javier [...]