Las matem¨¢ticas que nos dicen c¨®mo de dif¨ªcil es un problema

Los ordenadores est¨¢n cada vez m¨¢s presentes en nuestro d¨ªa a d¨ªa y nos ayudan a desarrollar numerosas tareas, como, por ejemplo, encontrar la ruta m¨¢s corta a un destino. Afortunadamente, existen algoritmos bien conocidos para resolver de forma eficiente gran parte de estos problemas pr¨¢cticos. Sin embargo, para muchos otros problemas relevantes, no se conoce ning¨²n algoritmo que ofrezca una respuesta correcta en un tiempo razonable y no se sabe si es posible que lo haya, incluso cuando s¨ª es posible verificar, de forma sencilla, que una posible soluci¨®n es o no correcta.

Consideremos, por ejemplo, un grafo, es decir, una estructura matem¨¢tica constituida por v¨¦rtices (puntos) conectados por aristas (l¨ªneas). En un grafo, un camino es una forma de llegar de un punto a otro siguiendo sus artistas. Un problema ser¨ªa determinar si en un grafo cualquiera hay o no un camino que pasa por cada arista una y solo una vez ¨Cllamado camino de Euler¨C. Para resolver esta cuesti¨®n existe un algoritmo eficiente que, de hecho, en caso afirmativo, encuentra el camino de Euler.

En teor¨ªa de la computaci¨®n, un algoritmo es eficiente si se ejecuta en un tiempo proporcional de ¡°forma polin¨®mica¡± al tama?o del problema de partida. Por ejemplo, en nuestro caso, si n es el n¨²mero de v¨¦rtices del grafo y el tiempo empleado por el algoritmo para dar con la soluci¨®n se expresa como un polinomio de n, por ejemplo, n? o 2n? + 7, es eficiente; si el tiempo tiene una forma no polin¨®mica, como 2?n, no es eficiente.

Camino hamiltoniano

Modifiquemos un poco la pregunta anterior: ahora queremos saber si, en cualquier grafo dado, existe un camino que pasa por cada v¨¦rtice y lo hace solo una vez, lo que se denomina un camino hamiltoniano. Un algoritmo sencillo para resolver este problema ser¨ªa comprobar todos los posibles caminos del grafo y ver si alguno es hamiltoniano. Si el grafo de partida tiene cuatro v¨¦rtices, entonces habr¨ªa que analizar 24 caminos posibles ¨Co la mitad de ellos, haciendo uso de la simetr¨ªa¨C, lo que es factible. Pero si tomamos un grafo de 30 v¨¦rtices, el n¨²mero de posibles caminos a estudiar es mayor que el n¨²mero de microsegundos ¨Cla millon¨¦sima parte de un segundo¨C que se estima que han transcurrido desde el Big Bang. En la pr¨¢ctica, este problema es intratable.

Podr¨ªamos pensar que, usando alg¨²n truco, como el que se emplea para resolver el problema del camino de Euler, ser¨ªa posible dise?ar un algoritmo m¨¢s eficiente que el anterior. Desgraciadamente, pese a la gran cantidad de trabajo invertido en el tema, de momento no se conoce ning¨²n algoritmo que sea sustancialmente m¨¢s eficiente que el indicado. Sin embargo, si alguien asegura que tiene un camino hamitoniano para el grafo de 30 v¨¦rtices es f¨¢cil comprobar, incluso a mano, que efectivamente lo sea.

Todos los problemas en los que es f¨¢cil verificar que una posible soluci¨®n es correcta pertenecen a la clase NP, que incluye tanto el problema del camino de Euler como el del camino hamiltoniano. Esta clase incluye otra, llamada P, formada por los problemas cuya soluci¨®n se puede obtener mediante un algoritmo eficiente, como el problema del camino de Euler. Aunque sabemos que P est¨¢ incluido en NP, de momento no se sabe si estas dos clases son iguales, es decir, no sabemos si todos los problemas de NP pueden resolverse con algoritmo eficiente (que podr¨ªamos no conocer de momento). Esta pregunta se denomina el problema de P vs NP.

La cuesti¨®n, central en el campo de la teor¨ªa de la complejidad computacional, es uno de los siete problemas del milenio seleccionados por el Instituto Clay y su resoluci¨®n est¨¢ premiada con un mill¨®n de d¨®lares

Daniel Gra?a, profesor de la Universidad del Algarve

La cuesti¨®n, central en el campo de la teor¨ªa de la complejidad computacional, es uno de los siete problemas del milenio seleccionados por el Instituto Clay y su resoluci¨®n est¨¢ premiada con un mill¨®n de d¨®lares. La opini¨®n general entre los expertos es que estas clases son diferentes, pero, pese a la gran cantidad de investigaci¨®n desarrollada al respecto, nadie ha sido capaz de demostrarlo por ahora.

Una de las estrategias empleadas para abordar el tema, desde la d¨¦cada de 1970, es basarse en los problemas NP-completos que son, en cierto modo, los problemas m¨¢s dif¨ªciles de la clase NP. Un ejemplo de esta clase de problemas es el del camino hamiltoniano, pero existen muchos otros de diverso tipo.

Lo interesante de este enfoque es que todos los problemas NP-completos son computacionalmente equivalentes, lo que significa que si se encontrara un algortimo eficiente para resolver alguno de ellos, se sabr¨ªa que es posible resolverlos todos de forma eficiente ¨Ctambi¨¦n el resto de problemas NP, que son m¨¢s sencillos¨C y, por tanto, P ser¨ªa igual a NP. Rec¨ªprocamente, si se demostrara que un problema NP-completo no puede ser resuelto por ning¨²n algoritmo eficiente, entonces quedar¨ªa determinado que ninguno de ellos puede ser resuelto por un algoritmo de este tipo y, por tanto, P ser¨ªa diferente a NP.

Pese a lo prometedor del planteamiento, por el momento, parece que ni este, ni ning¨²n otro acercamiento al problema han sido suficientes para resolver P vs NP. De hecho, algunos resultados sugieren que nuestras herramientas matem¨¢ticas actuales no son lo suficientemente sofisticadas para enfrentar problemas como este.

En esencia, esta cuesti¨®n trata de determinar si es m¨¢s dif¨ªcil encontrar soluciones ¨Clo que se puede hacer en los problemas de P¨C que comprobar que un resultado es una soluci¨®n correcta. Saber si esto es as¨ª o no podr¨ªa tener implicaciones profundas en las matem¨¢ticas y en la ciencia en general.

Por ejemplo, podr¨ªamos saber si es m¨¢s dif¨ªcil obtener una nueva demostraci¨®n matem¨¢tica que comprobar que una demostraci¨®n dada est¨¢ bien. O si es m¨¢s complicado formular una teor¨ªa que sea coherente con los datos experimentales disponibles que verificar la coherencia de una teor¨ªa dada. Generalmente, creemos que es as¨ª: la creatividad que requiere dar con una nueva demostraci¨®n o teor¨ªa es m¨¢s costosa que la rutina de revisarla. Sin embargo, si se demostrase que P=NP, tendr¨ªamos que cuestionar estas creencias. En cualquier caso, la resoluci¨®n del problema P vs NP tendr¨¢ un gran impacto tanto en el desarrollo de un nuevo tipo de matem¨¢ticas como en muchas aplicaciones pr¨¢cticas.

Daniel Gra?a es profesor de la Universidad del Algarve e investigador del Instituto de Telecomunicaciones (Portugal).

Edici¨®n y coordinaci¨®n: ?gata A. Tim¨®n G Longoria (ICMAT).

Caf¨¦ y Teoremas es una secci¨®n dedicada a las matem¨¢ticas y al entorno en el que se crean, coordinado por el Instituto de Ciencias Matem¨¢ticas (ICMAT), en la que los investigadores y miembros del centro describen los ¨²ltimos avances de esta disciplina, comparten puntos de encuentro entre las matem¨¢ticas y otras expresiones sociales y culturales y recuerdan a quienes marcaron su desarrollo y supieron transformar caf¨¦ en teoremas. El nombre evoca la definici¨®n del matem¨¢tico h¨²ngaro Alfred R¨¦nyi: ¡°Un matem¨¢tico es una m¨¢quina que transforma caf¨¦ en teoremas¡±.

Puedes seguir a MATERIA en Facebook, Twitter e Instagram, o apuntarte aqu¨ª para recibir nuestra newsletter semanal.