El problema que los inform¨¢ticos no han podido resolver en 45 a?os

?Qu¨¦ diantres se esconde tras la pregunta '?P=NP?', y por qu¨¦ parece ser tan importante para los inform¨¢ticos? Se trata de una pregunta, todav¨ªa sin respuesta desde 1971, a?o en que fue planteada, que trae de cabeza a los inform¨¢ticos. Si fuera P¡ÙNP, las cosas seguir¨ªan m¨¢s o menos igual, pero si fuera P=NP, entonces muchas cosas cambiar¨ªan y no necesariamente para mejor. Veamos por qu¨¦.

Gran parte de la ciudadan¨ªa tiende a pensar que los computadores pueden resolver todos los problemas, y que los que no pueden resolver hoy, podr¨¢n hacerlo ma?ana, porque su potencia de c¨¢lculo crece continuamente. Los inform¨¢ticos sabemos en cambio, que una infinidad de problemas de c¨®mputo no tendr¨¢n soluci¨®n nunca (los llamamos problemas indecidibles), y que para otros problemas existen algoritmos que los resuelven, pero empleando para ello tanto tiempo de c¨¢lculo, que a efectos pr¨¢cticos es como si fueran irresolubles (los llamamos problemas intratables). Los problemas que resuelven los computadores en un tiempo razonable los llamamos polinomiales, y todos ellos se agrupan en la llamada clase P. Se dicen as¨ª porque su tiempo de c¨®mputo est¨¢ descrito por un polinomio en el tama?o de los datos. Por ejemplo, el problema de multiplicar dos matrices de n filas y n columnas se puede resolver utilizando menos de n³ multiplicaciones. Ninguno de los problemas intratables est¨¢ en la clase P.

M¨¢s informaci¨®n

El joven que se enfrenta al problema matem¨¢tico del mill¨®n de d¨®lares

Lo imposible

Hay otra clase de problemas, a la que llamamos NP, cuya definici¨®n est¨¢ hecha de tal manera que incluye todos los problemas de la clase P, pero tambi¨¦n otros muchos que se comportan de un modo intrigante. Uno de esos problemas es el llamado problema del viajante de comercio: dado un mapa de carreteras, consiste en encontrar el camino m¨¢s corto para visitar n ciudades una sola vez y volver al punto de origen. Para estos nuevos problemas de la clase NP, los mejores algoritmos que se conocen tienen un coste similar al de los problemas intratables, pero nadie ha podido demostrar que no existan algoritmos polinomiales para ellos. Tampoco nadie ha demostrado que sean intratables. Est¨¢n, por decirlo as¨ª, en una especie de limbo inform¨¢tico: no se sabe si son polinomiales, o si son intratables. La teor¨ªa desarrollada en estos a?os ha llegado sin embargo a alguna conclusi¨®n ¨²til: ha definido una subclase de la clase NP, la subclase de los problemas NP-completos, en la cual se agrupan los problemas m¨¢s costosos de la clase NP, de tal forma que, si para uno cualquiera de dichos problemas se encontrara un algoritmo polinomial, entonces todos ellos se resolver¨ªan en tiempo polinomial y adem¨¢s la clase NP colapsar¨ªa a P, es decir tendr¨ªamos la igualdad P=NP. M¨¢s a¨²n, si se demostrara que uno solo de los problemas NP-completos es intratable, entonces todos ellos lo ser¨ªan y tendr¨ªamos la desigualdad P¡ÙNP.

La criptograf¨ªa actual depende de un problema de la clase NP, el de la descomposici¨®n en factores de un n¨²mero, para el que no tenemos algoritmos eficientes

Las consecuencias de esto ¨²ltimo no ser¨ªan muchas: simplemente dejar¨ªamos de buscar algoritmos polinomiales para una serie de problemas interesantes, porque sabr¨ªamos con seguridad que tales algoritmos no existen. En cambio, si fuera P=NP, habr¨ªamos encontrado algoritmos polinomiales para todos esos problemas. La parte buena de ello es que podr¨ªamos resolver, en tiempos muy cortos, problemas del viajante con miles de ciudades y otros cientos de problemas ¨²tiles para los que hoy tenemos algoritmos muy costosos, y eso ser¨ªa beneficioso para la industria, las comunicaciones y el desarrollo en general. La parte mala es que las claves criptogr¨¢ficas se descifrar¨ªan con gran facilidad, y muchas cuentas bancarias y comunicaciones cifradas quedar¨ªan expuestas a los amigos de lo ajeno.

En efecto, la criptograf¨ªa actual depende de un problema de la clase NP, el de la descomposici¨®n en factores de un n¨²mero, para el que no tenemos algoritmos eficientes. El m¨¢s eficiente de todos tard¨® 18 meses en descomponer en factores un n¨²mero de 200 cifras decimales, que son los que se usan habitualmente en criptograf¨ªa. La seguridad de las claves descansa precisamente en esta dificultad, hoy por hoy insalvable. Si fuera P=NP, entonces la descomposici¨®n en factores pasar¨ªa a ser un problema polinomial y se podr¨ªa resolver eficientemente. La criptograf¨ªa tendr¨ªa que ingeni¨¢rselas para basar la seguridad de sus claves en la resoluci¨®n de alg¨²n problema realmente intratable, porque los de la clase NP habr¨ªan pasado todos ellos a la categor¨ªa de eficientes.

Ricardo Pe?a Mar¨ª es catedr¨¢tico de la Universidad Complutense de Madrid.

Cr¨®nicas del Intangible es un espacio de divulgaci¨®n sobre las ciencias de la computaci¨®n, coordinado por la sociedad acad¨¦mica SISTEDES (Sociedad de Ingenier¨ªa de Software y de Tecnolog¨ªas de Desarrollo de Software). El intangible es la parte no material de los sistemas inform¨¢ticos (es decir, el software), y aqu¨ª se relatan su historia y su devenir. Los autores son profesores de las universidades espa?olas, coordinados por Ricardo Pe?a Mar¨ª (catedr¨¢tico de la Universidad Complutense de Madrid) y Macario Polo Usaola (profesor titular de la Universidad de Castilla-La Mancha).