Supongamos que pedimos a un mesero que nos arme un menú (según la ilustración) que cueste $15.05 dólares exactamente. ¿Le estamos pidiendo algo fuera de sus capacidades y posibilidades? Probablemente no. Veamos porqué.
Sabemos que los algoritmos toman diferentes cantidades de tiempo para completar sus tareas, pero lo que realmente importa en esta teoría de la complejidad es cómo se escala la problemática.
En el problema del vendedor viajante, buscamos una ruta para que visite las ciudades a las que está asignado una sola vez, en donde la distancia total recorrida no exceda cierto valor L. Cabe decir que el problema pide estrictamente encontrar una L que sea mínima, lo que lo vuelve aún más difícil.
Por supuesto que para un par de ciudades es fácil resolverlo. Se usan todas las posibles rutas y se elige la que tenga una distancia menor. El punto es que cada vez que se llega a una ciudad, el número de caminos puede crecer significativamente.
Este incremento en el trabajo que se necesita crece proporcionalmente a medida que aumenta el tamaño del problema. Lo que significa que tarde o temprano usted se hallará en un punto en donde la interrogante esté por encima de sus posibilidades de cálculo.
Así, por ejemplo, si se le pide hallar la trayectoria más corta considerando 100 ciudades, es claro que tendrá que hacer mucho trabajo.
Sin embargo, hay un lado interesante de los problemas de este tipo, por ejemplo, si usted da una solución para las rutas de 100 ciudades, ésta puede verificarse rápidamente. Basta con confirmar que se visita cada ciudad y que la distancia recorrida es menor que L. Esto lo califica como un problema del tipo NP.
La N significa NO determinístico y la P es de polinomio. Así, la idea es que aunque la dificultad del problema original pueda crecer más rápido que cualquier potencia del tamaño (es decir, que crezca más rápido que el polinomio del tamaño que se elija), verificar una solución hallada al azar, es decir, no determinística, es polinomial en términos del tamaño del problema. Para muchos, cuando esto pasa, tenemos que NP=P, esto es, hay soluciones más rápidas para los problemas NP que simplemente no hemos encontrado aún.
Entonces, ¿qué son los problemas NP-completos?
Un problema NP-completo es uno que puede convertirse en otro problema NP en un tiempo polinomial razonable. Así, si se tiene un algoritmo P para una incógnita NP-completa, entonces se tiene un algoritmo P para todos los problemas NP y NP=P. Se puede entonces pensar en un ejercicio de este tipo como una representación universal de estos casos.
Finalmente, ¿qué hay acerca de los problemas NP-difíciles?
Un problema NP-difícil es cualquier tipo de problema, no necesariamente en el conjunto de los NP, que puede ser reducido a uno NP-completo en un tiempo polinomial razonable. En este sentido, los problemas NP-difíciles son al menos tan difíciles como los problemas NP-completos, pero podrían ser mucho más difíciles. Por ejemplo, supongamos que se tiene una solución exponencial a un problema NP-difícil que puede ser convertida a una solución exponencial de un problema NP. Se tiene un tiempo exponencial de solución al problema NP, pero puede que tenga otra solución que trabaje en tiempo polinomial.
Por ejemplo y para ilustrar el asunto: en el problema del vendedor viajero, encontrar la trayectoria más corta es NP-difícil, porque éste debe dar la solución al problema NP-completo de descubrir una trayectoria menor que L. Sin embargo, el problema para dar con una trayectoria menor que L podría ser un problema más sencillo que lograr la trayectoria mínima.
Así pues, en el problema del mesero, en donde se busca que éste encuentre una combinación de los diferentes platillos que den exactamente un costo de $15.05 dólares, hablamos de una nueva versión del problema de la mochila en donde se busca llenarla con objetos que en total sumen una cantidad definida de kilos. Se sabe que el problemas de la mochila es NP-completo, y si el problema es lo suficientemente grande, podría llevar mucho tiempo resolverlo pero de nuevo, cualquier solución puede verificarse rápidamente.
Con estas consideraciones… ¿tendría que esperar el mesero una eternidad para hallar una solución? No para el caso del menú que se presenta en este problema. Probablemente daría con la solución en un tiempo corto, es decir, difícilmente puede considerarse un problema NP-difícil, porque en este caso se supone que le llevaría siempre más tiempo que el posible.
Fuente: i-programmer