Los problemas que no merece la pena intentar resolver

Si se dispone de una mochila de un tamaño determinado, pero existen restricciones en cuanto al peso que puede contener y se tiene que llenar con X objetos que pesan más de esa cifra, la solución podría parecer fácil. Lo que cualquiera haría, como se hace habitualmente al llenar el maletero de un coche, es intentar encajar las piezas hasta conseguir meter las máximas posibles con el peso más cercano al tope permitido. 

Este problema, que parece sencillo, no lo es tanto y pertenece a la categoría de los denominados problemas NP-completos. En otras palabras, son aquellas cuestiones para las que no existe un algoritmo computacional, una fórmula que se pueda aplicar para resolver todos los casos. En realidad, es incorrecto decir que no existe, se ha de hablar, más bien, de que no perece la pena buscarlo. Aunque nos pueda parecer fácil, imaginemos ahora que las piezas que tenemos que encajar son muchísimas y de muy distintos pesos. ¿Cuánto se tardaría en llegar a la fórmula perfecta?

La propuesta de no hacer

Ante esta situación, un matemático estadounidense estableció en la década de 1970 lo que había que hacer: dejar de intentar resolverla. El científico en cuestión es Stephen Arthur Cook, que este martes ha sido galardonado con el Premio Fundación BBVA Fronteras del Conocimiento en la categoría de Tecnologías de la Información y la Comunicación.

Lejos de apelar a la falta de tesón, Cook lleva toda su carrera llamando a la eficiencia. De hecho, lo que el jurado ha premiado -con 400.000 euros- es "su importante papel a la hora de determinar qué pueden los ordenadores resolver de forma eficiente y qué no".

El director del Instituto de Investigación en Inteligencia Artificial del Consejo Superior de Investigaciones Científicas (CSIC), Ramón López de Mántaras, explica a EL ESPAÑOL que el tipo de problemas que Cook definió como NP-completos -al que pertenece el famoso ejemplo de la mochila- no son irresolubles. "Hay cosas en las que no merece la pena invertir tiempo y para las que quizás sea mejor buscar una solución aproximada", comenta.

El investigador asturiano destaca que hay muchos ámbitos en los que nos encontramos problemas NP-completos, como el diseño de fármacos a partir de proteínas. Por eso es tan complejo desarrollar fármacos para ciertas enfermedades, porque no existe un algoritmo universal para hacerlo.

También destaca que es difícil establecer a qué categoría de eficiencia en la resolución pertenece cada problema.

Problemas del Milenio

El trabajo de Cook, que ha expresado en teleconferencia desde la Universidad de Toronto -donde es catedrático- su agradecimiento por el premio, ha dado lugar también a todo un reto para los matemáticos del mundo, una de las principales cuestiones sin resolver de las matemáticas, llamada de "P versus NP". Se trata de uno de los siete Problemas del Milenio del Clay Mathematics Institute (EEUU), cuya resolución se premia con un millón de dólares.

Porque además de definir los problemas NP como "aquellos que podrían ser en principio resueltos por un ordenador, pero la máquina tardaría tanto que el Sol moriría antes", el investigador definió también los P, que sí pueden ser resueltos en un tiempo razonable. Pero lo que se plantea en el desafío matemático es qué pasaría si de descubriera una manera de resolver los primeros problemas. Aunque todo el mundo da por hecho que la tesis de Cook es correcta, "es imposible probar que son irresolubles", comenta López de Mántaras, miembro del jurado que otorgó el premio.

Si alguien lo consiguiera, todo se pondría patas arriba, ya que significaría que cualquier problema NP podría solucionarse. Esto tendría todo tipo de implicaciones y afectaría incluso al sistema de encriptado.

Como subraya el investigador español, los grandes avances en informática no han servido para avanzar en la resolución de este problema. "Esto es cuestión de lápiz y papel", bromea.