eLKcro Team

Como todos saben, sin la matemática discreta la informática no existiría y ahora no podría estar escribiendo esto, capaz que anduviera jugando al luche … en fin.. les presentare uno de los problemas actuales de la computación que es el famoso P vs NP

Para empezar debo explicarles que esto se trata de la complejidad que tiene resolver un problema de desición ya sea en tiempo polinomial (P) o en tiempo no polinomial (NP), por ejemplo:

Supongan que tienen una lista de numeros y quieren saber si el primer numero es el menor de esta lista, para hacerlo solo deberan recorrer su lista n-1 veces. Por lo tanto el algoritmo es de orden n O(n) que es de tipo polinomial.

Ahora supongan que tienen un grupo de n ciudades y conocen las distancias entre todas ellas lo que les daria una matriz de nxn refleja, lo que se conoce como un grafo dirigido y conexo. En fin, para calcular la minima distancia que pase por todas las ciudades necesitaremos todas las permutaciones posibles que serán n!

Así , la resolución de este problema es de tipo exponencial, es decir a medida que aumenta el numero de nodos o ciudades en este caso mucho mayor sera el tiempo de cómputo.

Si cada cálculo durara 1 microsegundo, para 10 ciudades tendriamos un resultado en 3 segundos, para 11 ciudades un poco mas de medio minuto y para 20 ciudades.. adivinen….77.146 años INCREIBLE!!! (es la magia del crecimiento exponencial)

Aunque hay métodos que logran buenas aproximaciones aún no existe un algoritmo que calcule este tipo de problermas de forma eficiente.

¿Qué aplicacion tiene esto? Las empresas de correos se ahorrarían millones de dólares al año si encontrasemos la solución y esa es sólo una aplicación que se me ocurrio para estar acorde al ejemplo que di.

Como una notita les cuento que existe un premio de un millón de dólares al que desee plantea un algoritmo para resolver un problema NP-completo a un problema P si les resulta me avisan