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 –llamado camino de Euler–. 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 2n, 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 –o la mitad de ellos, haciendo uso de la simetría–, 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 –la millonésima parte de un segundo– 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 –también el resto de problemas NP, que son más sencillos– 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 –lo que se puede hacer en los problemas de P– 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).
