problemas del milenio

P versus NP[editar]
Artículo principal: P versus NP
Consiste en decidir si la inclusión entre las clases de complejidad P y NP es estricta.

Las matemáticas actuales noposeen la suficiente capacidad para poder distinguir problemas de tipo P y NP, para los cuales es necesario desarrollar algoritmos bastante complejos. El problema en sí reside en queexisten problemas que no pueden resolverse en tiempo polinomial en una máquina determinista, es decir, no son abarcables. La aritmética actual tiene límites a la hora derealizar algunos cálculos que ni los ordenadores más potentes pueden realizar en un tiempo "razonable", es decir, del orden de las n^2 ó n^3 operaciones. Sin embargo el carácterexponencial de algunos problemas hace que actualmente su tratamiento sea inviable.

Se piensa que estos problemas podrían estar relacionados con el teorema de incompletitud de Gödel.Según parece, ciertos enunciados matemáticos, entre los que se incluyen los que se refieren a cotas inferiores de tiempo de cifrado, no se pueden demostrar dentro del marco de laaritmética de Peano, que es la forma estándar de la aritmética.

Un ejemplo sería: si queremos determinar todas las formas posibles de asignar 70 personas a 70 trabajosdiferentes de forma que todas las personas tengan un trabajo y ninguna plaza quede vacante, no sería difícil (para quien posea una mínima base matemática) establecer la solución: 70!(setenta factorial). Sin embargo, el cálculo de este número sería equivalente a un número del orden de 10 elevado a la centésima potencia, lo que significa que ni en la edad deluniverso podría resolverse computacionalmente este problema.

Hoy en día el estudio de este problema se plantea como la resolución o búsqueda de los límites en la computación.