¿Es P=NP? ¿Lo sabremos algún día?

La Vanguardia, 23 de Junio de 2003
-
Las cumbres pendientes
MIQUEL MOLINA. Barcelona Más allá de su utilidad práctica, resolver los grandes enigmas matemáticos permitiría avances clave en el conocimiento
Pocos enigmas pendientes tienen una utilidad práctica

Imaginemos que alguien quiere pintar una habitación de un color exclusivo que no aparezca en ningún catálogo. Y que se encierra unos días con 50 botes de pintura y, al final, lo consigue. El objetivo es relativamente fácil, pero ¿cómo se las arreglará el siguiente inquilino para, utilizando los mismos botes, fabricar el mismo color y disimular así los agujeros dejados por los tacos que sujetaban los cuadros, cuando las combinaciones de colores son, si no infinitas, sí absolutamente inabarcables? ¿Se puede encontrar la combinación?

El problema, derivado de la inexistencia de un superordenador capaz de resolverlo por la fuerza bruta, es lo que se conoce como un problema NP, un reto para el que se sospecha que no hay solución, aunque nadie ha demostrado aún que sea imposible que exista. ¿Es P=NP, entendiendo por P "tiempo polinómico" y por N "no determinista"?

El enigma, de enunciado aparentemente simple, es una de las grandes cuestiones pendientes de las matemáticas, como lo son la hipótesis de Riemann, las ecuaciones de Navier-Stokes o la conjetura de Goldbach. De entre todas las preguntas sin respuesta, siete han sido seleccionadas por el Clay Mathematics Institute de Massachusetts (EE.UU.) para su premio del Milenio, dotado con un millón de dólares para cada solución.

Desde que se hizo pública la convocatoria en la primavera del 2000, sólo uno de los enigmas parece en vías de resolverse: la conjetura de Poincaré, útil para la física teórica y la descripción del universo. En abril, el ruso Grigori Perelman emergió de ocho años de enclaustramiento y anunció su solución a la conjetura, pendiente ahora de un proceso de verificación. Es de suponer así que hay otros matemáticos o equipos de investigadores trabajando para seguir los pasos del ruso y, sobre todo, los de Andrew Wiles, el profesor que en 1994 dio respuesta al último teorema de Fermat, quien había planteado la diabólica pregunta en el margen de un libro antes de morir en 1665.

¿Pero hay alguien trabajando en España para resolver los grandes enigmas? "Creo que todos trabajamos en este mundo de las ideas, podemos decir que todos, de una manera o de otra, trabajamos en ello, al menos si no nos limitamos a los siete problemas del Clay Institute", responde el matemático de la Universitat Politècnica (UPC) Sebastià Xambó. "Pero si se trata -añade- de decir si conozco a alguien que se haya propuesto explícita y públicamente resolver la hipótesis de Riemann, la conjetura de Hodge o el problema de la complejidad computacional, entonces mi respuesta es que no lo sé."

Enrique Gracián, matemático y periodista científico, añade que, en cualquier caso, si alguien se ha puesto seriamente a investigar en ello no lo confesará nunca, porque "a nadie se le ocurriría ir diciendo por ahí algo tan pretencioso como me encierro para resolver la conjetura de Poincaré".

Pocos de los grandes enigmas pendientes tienen utilidad práctica. Las del P versus NP son obvias, como también están claras las de la resolución de las ecuaciones Navier-Stokes, que permitiría actuar contra las turbulencias que padecen los aviones. Pero los matemáticos no tienen dudas sobre lo provechoso que es enfrentarse a retos en ocasiones incluso hasta poéticos -como considera Gracián el trabajo de Wiles sobre Fermat- cara a aplicaciones posteriores a problemas concretos de nuestro tiempo. El profesor Xambó lo ilustra de la siguiente forma:
"Nos puede servir como ejemplo la teoría de Galois sobre la solución de las ecuaciones algebraicas. Sin un Clay Institute premiando a quien consiguiera resolver el enigma, tuvo que escribir sus resultados la noche antes de un duelo fatídico y, por circunstancias históricas que no viene al caso calificar, no fueron entendidas por la comunidad matemática hasta muchos años después. Pero lo cierto es que entre las consecuencias de las ideas de Galois está la construcción de los llamados cuerpos de Galois, que son una herramienta indispensable en la corrección de los errores producidos en la transmisión de información, como por ejemplo en la lectura de la música de los discos compactos. Y lo mismo podríamos decir de cualquier otro momento en el que se ha resuelto un problema sustantivo, desde Pitágoras hasta Wiles pasando por Newton, Gauss, Riemann o Einstein."

Otros enigmas entran en el terreno de lo romántico o literario. Así, aún hay quien no renuncia a creer que el número pi se rige por algún patrón, pese a que ya haya sido calculado hasta miles de millones de dígitos sin que se detecte ninguna norma y de que se hayan publicado estudios que demuestran que supera todos los tests de aleatoriedad.

Para Enrique Gracián, los grandes problemas que hemos heredado del pasado serán los últimos con un enunciado relativamente simple y que, en algún caso, se podrán resolver sin recurrir a los ordenadores, en un contexto en el que las matemáticas avanzan hacia una extrema complejidad. Pero, en su opinión, más allá de concentrar el esfuerzo en la resolución de estos grandes mitos, se impone debatir el tipo de matemáticas que se enseña actualmente a los niños. "Tratándose de una disciplina tan cambiante, ¿estamos seguros de que lo que le empezaremos a enseñar hoy a una niña de siete años será lo que le convendrá saber cuando tenga 20?"

Volver