NP-completo - Una guía rápida

Este artículo es una guía del significado de "NP-completo". No tiene la intención de dar una definición exacta, pero este texto debería de ayudarte a entender el concepto.

Estas solo son mis ideas personales y no son muy "rigurosas".

Esto va del "tiempo de resolución"

Si mides cuánto tarda un programa de ordenador en resolver problemas más y más difíciles, como ordenar una lista de 10 objetos, 20 objetos, 30 objetos, etc., entonces puedes dibujar en un gráfico los tiempos y así tienes una función.

Pero si el tiempo aumentara exponencialmente o factorialmente, o algo por encima de lo que crecería un polinomio, no estaría en "P". No es resoluble en tiempo "polinomial".

P: puede ser resuelto en tiempo Polinomial.
 (El tiempo que tarda está definido por un polinomio)

La Computadora Asombrosa puede hacer cosas que las normales no pueden

Ahora bien, el "N" de "NP" se refiere al hecho de que no estás limitado por el funcionamiento normal de las computadoras, que es paso a paso. El "N" en realidad quiere decir "no determinista". Esto significa que lo podría hacer una computadora asombrosa que puede hacer varias cosas a la vez o adivinar el camino correcto de alguna manera, o algo así.

Así que esta computadora "N" puede resolver muchos más problemas en tiempo "P", por ejemplo podría clonarse a sí misma cuando hiciera falta.

No es una supercomputadora (esas solo son computadoras normales), es una computadora "no determinista", ¡yo la llamo la Computadora Asombrosa para que te hagas una idea!

Así los programas que tardan muchísimo más cuando el problema se complica (o sea, no en "P") se podrían resolver rápidamente con esta asombrosa computadora "N" así que decimos que está en "NP". O sea que "NP" significa "lo podemos resolver en tiempo polinomial si podemos romper las reglas normales de la computación paso a paso".

NP:se puede resolver en tiempo Polinomial usando un
método No determinista.
(también incluye P problemas)

 

La Computadora Asombrosa también puede hacer lo que hacen las computadoras normales

Como la computadora asombrosa "N" puede hacer lo que hacen las computadoras normales, sabemos que los problemas "P" también están en "NP".

Así que los problemas fáciles están en "P" (y en "NP"), pero los difíciles de verdad solo están en "NP", y se llaman "NP-completos".

Es como decir que hay cosas que puede hacer la Gente normal ("G"), hay cosas que puede hacer la Gente Super ("GS"), y cosas que solo la Gente Super puede ("GS-completo").

NP-completo: se puede resolver en tiempo Polinomial
solo usando un método No determinista.

A lo mejor el NP-completo no dura

Ah, una cosa más, se cree que si alguien consigue alguna vez un problema "NP-completo" en tiempo "P", entonces todos los problemas "NP-completos" se podrían resolver usando el mismo método, así que todo el conjunto de problemas "NP-completos" dejaría de existir.

El problema del viajante

El ejemplo clásico de problema "NP-completo" es el problema del viajante.

Imagina que tienes que visitar 5 ciudades en un viaje de negocios. Conoces todas las distancias. ¿Cuál es el viaje más corto que puedes hacer volviendo al punto de partida? ¿ABCEDA? ¿ADECBA?

Una solución muy clara es comprobar todas las posibilidades.

Pero esto solo funciona bien si el problema es pequeño. Y si añades una ciudad nueva tienes que probar otra vez todas las combinaciones.

Así que este método requiere "tiempo factorial": t = n!

(En realidad sería t = (n-1)! pero sigue siendo factorial).

Digamos que el programa pudiera resolver el problema de 20 ciudades en 1 segundo, entonces

• 21 ciudades llevarían unos 21 segundos.
• Y 22 ciudades llevarían unos 462 segundos (más de 7 minutos),
• y 30 ciudades llevarían 3 millones de años. ¡Ay!

Por suerte, hay maneras especiales de dividir el problema en subproblemas (llamadas "programación dinámica"), pero aun así la mejor necesita tiempo exponencial: t = 2ⁿ (2 con exponente n)

Así, un programa que resolviera el problema de 20 ciudades en 1 segundo tardaría unos 10 minutos en resolver el de 30 ciudades y para 60 ciudades tardaría 35,000 años.

Pero si tuviéramos la "Computadora Asombrosa" de más arriba, ella podría, por ejemplo, hacer copias de sí misma para comprobar todas las posibilidades, y quizás resolver el problema muy rápidamente.

NP-difícil

Cuando el método de solución de un problema se puede convertir en un método de solución NP-completo, se dice que es "NP-difícil" (o NP-complejo o NP-hard).

NP-difícil: tan difícil como cualquier problema de NP, o tal vez más difícil.

 

En cualquier caso, espero que esta introducción "informal" te haya venido bien... ahora puedes buscar algo más riguroso para leer.