P=NP

Bufff.... y más. Algo así como decir, anda mira, voy descifrar claves de bancos con mi algoritmo ultra eficiente mientras me fumo un cigarrillo. Vamos, algo trivial

En realidad, demostrar que P=NP es uno de los últimos (si no el último) problemas del millón de dólares que quedan (el que consiga demostrarlo se embolsa un millón de dólares). P se refiere a algoritmos polinómicos o con coste polinómico (o más correctamente, decidibles en tiempo polinómico). Si tenemos un problema de talla n, el tiempo en calcular la solución se puede calcular con una formula del tipo

anm + bnm-1 + ... + un2 + vn + w.

Un ejemplo de problemas polinómico es ordenar un vector (depende del algoritmo utilizado puede variar entre n² o nlog(n).

Además de algoritmos polinómicos, los hay exponenciales (2ⁿ) o cosas más bestias aún.

Los problemas NP (Polinómicos No deterministas) son problemas decidibles en tiempo exponencial, pero que se puede demostrar que una solución dada es correcta en tiempo polinómico. Además, dentro de los problemas NP, existen los llamados NP-Completos, más comúnmente llamados en ámbitos estudiantiles como "por culpa de este problema voy a tripitir TC". Dichos problemas NP-Completos son los más putas que te puedes encontrar dentro de los NP. Ejemplos de problemas NP-Completos son:

• Buscaminas
• Problema del viajante (Travel Salesman Problem): Dado un mapa de carreteras con varias ciudades en él, y con las distancias entre pueblos marcadas, encontrar el camino más corto para que el viajante pase por todas las ciudades, es NP completo porque, dado el número de ciudades n, el número de recorridos posibles es Gamma(n)/2 = (n-1!)/2, lo cual crece muy rápido.
• Problema de la mochila: Tenemos una mochila que puede soportar un peso total P. Tenemos también N objetos (n₁, n₂, ..., n_n) con sus pesos asociados (p₁, p₂, ..., p_n), de tal manera que n_i pesa p_i. Encontrar una manera de meter m objetos (m <= ||N||) cuyo peso total sea exactamente P.
• Planificador: Tenemos n procesadores, m procesos y un tiempo total T. Conseguir meter todos los procesos posibles en los n procesadores (cada procesador puede procesar un solo proceso a la vez) y acabar en un tiempo igual o inferior a T.