NP para no matemáticos

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

Estas sólo son  ideas vagas, pero ayudara a comprender el significado.

 

 

 “Tiempo de resolución”

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


La Computadora Asombrosa puede hacer cosas que las normales no pueden. 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”.

Ahora bien, la “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 la cual  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, 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”.   “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

A lo mejor el NP-completo no dura, 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”).

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.

Ejemplo: El problema del viajero

Por suerte, hay maneras especiales de dividir el problema en subproblemas (esto es  “programación dinámica”), pero aun así la mejor necesita “tiempo exponencial”: t = 2Digamos 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.

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.

Anuncios

2 comentarios en “NP para no matemáticos

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s