NP-completo - Una guía rápida

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

Estas sólo 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.

Por ejemplo el tiempo puede crecer como x², así que un problema que es el doble de difícil tarda 4 veces más.

Decimos que ese programa estaría en "P", que significa que el problema se resuelve en tiempo "polinomial". En ese caso el polinomio es:

t = x²

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".

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 sólo 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".

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 sólo 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 sólo la Gente Super puede ("GS-completo").

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 sólo 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 lleva "tiempo factorial": t = n!

 

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 = 2n

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.

¿Me pregunto si una red de tuberías podría servir? ¿Echar agua por arriba y ver por qué camino llega la primera gota a la parte de abajo?

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

 

Buscar :: Índice de Temas :: Sobre Nosotros :: Contáctanos :: Cita esta Página :: Privacidad

Copyright © 2011 Disfruta Las Matemáticas.com
Math is Fun Website