La teoría de la computación surgió con fuerza en los años 30 del siglo pasado, cuando Alonzo Church (1903-1995) y Alan Turing (1912-1954) demostraron de forma independiente que la respuesta al problema de la decisión de Hilbert era negativa. Planteado por Hilbert en 1928 el problema pregunta: ¿existe un algoritmo que pueda decidir en un número finito de pasos si una determinada fórmula puede ser demostrada a partir de un conjunto de axiomas dado?
La teoría de la computación está emparentada con la lógica matemática, y de ella fueron pioneros, aparte de Church y Turing, el mismo Gödel, von Neumann o Claude Shannon (1919-2001). Debido a la importancia creciente de los ordenadores en el mundo moderno, los problemas de computación se encuentran entre los más relevantes que enfrentan hoy los matemáticos; y el más relevante de todos consiste en determinar si son o no iguales las llamadas clases P y NP –lo que habitualmente se escribe como «¿P=NP?»–.
Grosso modo, se dice que un problema es de la clase P si hay un algoritmo que lo resuelva en un tiempo de computación polinomial del número de datos. En un problema NP, desconocemos si una resolución es posible en tiempo polinomial del número de datos, pero si nos dan una solución, entonces es posible comprobar que lo es en un tiempo polinomial del número de datos –aclaro que todas estas definiciones imprecisas se pueden precisar de manera totalmente satisfactoria usando lógica formal–. Un típico problema P es el del cálculo del máximo común divisor de dos números; el algoritmo de Euclides, por ejemplo, resuelve el problema en un tiempo del orden del cuadrado del número de cifras de los números. Un típico problema NP es el de encontrar los factores primos de un número; hoy en día no se sabe resolver ese problema en tiempo polinomial –lo que no quiere decir que no se pueda hacer–, pero si nos dan los factores del número, comprobar que efectivamente lo son requiere sólo su multiplicación –que se puede realizar en un tiempo del orden del cuadrado del número de cifras de los números–. La importancia de hacer la factorización de un número en tiempo polinomial es clave para la seguridad de las comunicaciones electrónicas basadas en la criptografía RSA, cuya seguridad precisamente se sustenta en que hoy por hoy no se conocen formas eficientes en tiempo para encontrar los factores primos de un número. Eso pueda dar una idea de la importancia que tiene decidir la solución del problema ¿P=NP?
La misma importancia de los matemáticos podría evaluarse de saber la solución del problema ¿P=NP?. En efecto, comprobar la corrección de la demostración matemática de un teorema es un problema de tipo P. Buscarla es un problema tan complicado que ni siquiera es NP, pero podemos hacer lo siguiente; dado un polinomio \(p\), llamamos \(I_p\) al conjunto de teoremas que admite una demostración de longitud acotada por ese polinomio en el número de símbolos necesarios para enunciar el teorema. Para cada polinomio \(p\), comprobar si un teorema está en \(I_p\) sí es un problema NP. De manera que si la clase de problemas P fuera igual a la NP, y la demostración fuera suficientemente constructiva, para cada polinomio \(p\) existiría un algoritmo que en tiempo polinomial nos permitiría encontrar una demostración de cada teorema en el conjunto \(I_p\). Si eso fuera así, uno estaría tentando de decir que los matemáticos habríamos perdido buena parte de nuestra utilidad.
El problema ¿P=NP? es uno de los siete problemas del milenio, por cuya solución el Instituto Clay ofrece un millón de dólares.
El Instituto Clay lo fundó en 1998 el magnate bostoniano Landon T. Clay. Aprovechando la conmemoración del año 2000 como año mundial de las matemáticas, el Instituto Clay seleccionó los siete retos todavía sin resolver que consideraba más fundamentales para las matemáticas, y se comprometió a pagar un millón de dólares a quien resolviera alguno de ellos. Entre los retos figuran la conjetura de Poincaré y la hipótesis de Riemann –los únicos que todos los matemáticos consultados incluyeron en sus listas–, y también el ¿P=NP?
La iniciativa del Instituto Clay imitaba la que tuvo David Hilbert en 1900, cuando propuso una lista de 23 problemas que, a su entender, eran los retos más importantes que las matemáticas debían afrontar en el siglo XX. Hilbert no era millonario y no ofreció dinero, ni mucho ni poco, a quien resolviera alguno de esos retos. «Poderoso caballero es don dinero», escribió nuestro Quevedo, pero Hilbert sabía que, cuando un matemático decide dejarse las neuronas buscando la solución de un problema profundo y difícil, no es dinero lo que busca. Así que no está nada claro que la recompensa del Instituto Clay sirva para acelerar la solución de los siete problemas del milenio; o quizá habría que decir que está clarísimo que de poco va a servir, si tenemos en cuenta el soberano desprecio que Perelman hizo al rechazar el millón de dólares a que era acreedor tras resolver la conjetura de Poincaré –el único de los siete problemas del milenio que ha sido por ahora resuelto–.
Referencias:
Antonio J. Durán, Crónicas matemáticas, Crítica, Barcelona, 2018.
Magnífico artículo del profesor Antonio J. Durán. Gracias