Matemáticas e informática: una pareja bien avenida
La cuestión ¿P=NP? está considerada uno de los siete problemas del milenio
La serie de televisión Stark Treck me gustaba mucho de pequeña, sobre todo por el personaje de Spock (Leonard Nimoy). Spock era medio humano, medio vulcano, y sufría un conflicto interno entre la razón y la lógica de su parte vulcana y la emoción e intuición de su parte humana. Ahora trabajo en informática, donde a menudo nos enfrentamos a problemas que necesitan de grandes dosis de intuición y razonamiento lógico para ser resueltos. Recordando a Spock, me pregunto cómo hubiera aplicado él la lógica para solucionarlos. Veamos dos ejemplos.
En el siglo XVIII, en la ciudad de Königsberg (hoy Kaliningrado), siete puentes conectaban las orillas del río Pregel con dos islas (Fig. 1), y se hizo popular el reto de encontrar un camino que recorriera la ciudad, saliendo y llegando al mismo sitio, atravesando una sola vez cada puente.
No sabemos cuánto tiempo se entretuvieron los vecinos buscando una solución, pero sí sabemos, gracias al matemático suizo Leonhard Euler, que tal circuito no existe.
Euler resolvió el problema de manera general en 1736, modelándolo mediante un grafo, y sus razonamientos dieron origen a la actual teoría de grafos. El grafo de Königsberg (Fig. 2) tenía cuatro vértices –A, B, C, D– representando las dos orillas y las dos islas, y siete aristas –a, b, c, d, e, f, g– para representar los puentes. El grafo facilitaba la exploración de todos los posibles caminos para comprobar si alguno cumplía la condición. Euler generalizó el problema y comprendió que el tiempo necesario para el análisis exhaustivo de todos los caminos de un grafo sería enorme al crecer el número de vértices y aristas. Simplificando un poco, si al llegar a un vértice podemos elegir entre dos caminos de salida y el grafo tiene n vértices, tendríamos 2n posibles caminos. La función exponencial crece muy rápidamente; en nuestra simplificación, para los cuatro vértices del grafo de Königsberg habría que comprobar 16 caminos (en realidad, son muchos más), pero si el grafo tuviera, por ejemplo, 100 nodos, el ordenador más potente del mundo necesitaría un tiempo muy superior a la edad del universo para analizar las 2100 rutas.
La genialidad de Euler fue evitar la búsqueda exhaustiva. Su mente lógica (hasta donde sabemos genuinamente humana y no vulcana) dedujo que, dado que al llegar a un vértice por una arista hay que continuar el circuito saliendo por otra (en total, dos aristas), para que exista una solución al problema, el grado de cada vértice –el número de aristas que tocan el vértice– debía ser par! Una solución simple y elegante a un problema complejo. Desde entonces, en honor a Euler, los caminos que comienzan y terminan en el mismo vértice y pasan una sola vez por cada arista se denominan circuitos Eulerianos. Si comienzan y terminan en vértices distintos, se denominan caminos Eulerianos.
Teorema de Euler: Un grafo contiene un circuito Euleriano si y solo si cada vértice tiene grado par.
Un grafo contiene un camino Euleriano si y solo si dos vértices tienen grado impar y el resto grado par.
Cuando intentamos dibujar las figuras A, B, C y D de la Fig. 3 sin levantar el lápiz del papel y sin pasar dos veces por la misma línea, estamos resolviendo el problema de encontrar un camino Euleriano. Gracias al teorema de Euler, sabemos a simple vista que es posible en el caso de las figuras A, B, y D, pero que es imposible para la figura C.
El segundo problema apareció en el siglo XIX. El astrónomo irlandés Sir William Rowan Hamilton ideó un juego denominado el juego icosiano. Proponía viajar a veinte ciudades, representadas por los vértices de un dodecaedro, siguiendo las aristas del mismo pero sin visitar la misma ciudad/vértice dos veces. El dodecaedro, de madera, tenía un clavito en cada vértice, donde se podía enrollar un cordel para representar el recorrido. El juego no tuvo éxito.
El problema es parecido al de los puentes. En lugar de buscar un circuito Euleriano (recorrer una sola vez cada arista), hay que buscar un circuito que pase una sola vez por cada vértice. Desde entonces, a este tipo de circuitos se les conoce como Hamiltonianos.
El juego sobre un dodecaedro tiene solución (Fig. 4), pero el problema general de decidir si un grafo contiene o no un circuito Hamiltoniano resulta ser extremadamente difícil: es un problema NP completo (véase el artículo de Ricardo Peña “El problema que los informáticos no han podido resolver en 45 años”). Fig. 4
Conocemos muchas familias de grafos para los que es muy sencillo decidir si existen circuitos Hamiltonianos; pero no tenemos un método general, como el de Euler, válido para cualquier grafo. En los casos difíciles, la única opción es hacer una búsqueda exhaustiva, usando un ordenador para evaluar todos los caminos posibles. Muchas personas que trabajamos en informática intentamos encontrar un método más inteligente para resolver este problema, o bien demostrar que tal método no existe. Si encontrásemos un método rápido, además de solucionar el asunto demostraríamos que P=NP, un dilema que nos trae de cabeza desde 1971. Si demostrásemos que no existe un método mejor que la búsqueda exhaustiva, entonces obtendríamos que P≠NP. La cuestión ¿P=NP? está considerada uno de los siete problemas del milenio.
¿Por qué es tan difícil el problema del circuito Hamiltoniano? Se trata de pasar una sola vez por cada vértice, mientras que en el caso Euleriano se trata de pasar una sola vez por cada arista. ¿Por qué este último resulta en cambio tan sencillo? ¿Dónde está la diferencia?
Como diría Spock, “fascinante” ¿No os parece?
Montserrat Hermo es profesora Titular de la Universidad del País Vasco
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, elsoftware), 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).
