Si no puedes con él, oponte a él

El pasado mes de mayo, Francisco Santos, catedrático de Geometrí­a y Topologí­a en la Universidad de Cantabria, refutó la Conjetura de Hirsch con un contraejemplo, un problema planteado hace más de medio siglo. Foros21 ha contactado con él en medio de uno de tantos viajes que le están llevando a presentar sus conclusiones por todo el mundo

¿Cuál es el interés, desde el unto de vista de la comunidad matemática, de demostrar la certeza o falsedad de una conjetura matemática? Un matemático, como cualquier científico, busca descubrir la verdad de las cosas. Eso se puede hacer explorando áreas nuevas, pero también reestudiando lo que otros dejaron sin decidir. Una conjetura es una afirmación que alguien hizo en algún momento, pero que no fue capaz de demostrar ni de “refutar” (demostrar su falsedad). En principio, cualquiera puede hacer una conjetura, y esta no tendrá más trascendencia; si es demasiado fácil, no tardará en resolverse. Aunque sea difícil, si no es relevante no pasará de ser una mera curiosidad a la que no mucha gente prestará atención. Pero de vez en cuando quedan abiertas conjeturas que son a la vez difíciles y relevantes. Un ejemplo reciente es la Conjetura de Poincaré, enunciada en 1905 y resuelta por Perelman en 2003, una afirmación que jugaba un papel básico en nuestro conocimiento de la geometría de dimensión tres. Otro ejemplo aún abierto es la llamada Hipótesis de Riemann, que tiene que ver con la distribución de los números primos (cuántos hay, con qué regularidad aparecen, etc). Conjeturas como esa son desafíos que los matemáticos tenemos siempre más o menos presentes. Aunque uno normalmente trabaja en problemas más prosaicos, esas conjeturas “están ahí” como puede estar para un alpinista un pico que nadie ha escalado o en el que aún se puede abrir una nueva vía. ¿En qué consiste la conjetura de Hirsch? La conjetura de Hirsch afirma que “si un poliedro está definido por N desigualdades lineales en D variables siempre ha de ser posible viajar de cualquier vértice a cualquier otro vértice recorriendo como mucho N menos D aristas”. En cierto modo, la conjetura pone un límite a cómo puede ser de complicada la estructura de un poliedro en base al número de ecuaciones necesarias para delimitarlo. Os pongo un ejemplo. Un cubo de dimensión tres se puede definir en coordenadas Cartesianas mediante las seis desigualdades siguientes: 0 ≤ x ≤ 1, 0 ≤ y ≤ 1, 0 ≤ z ≤ 1. Cada desigualdad nos da una de las seis caras del cubo. Puesto que N = 6 y D = 3, la conjetura de Hirsch para el cubo es que desde cualquier vértice podemos ir a cualquier otro vértice recorriendo una, dos o tres aristas. Es fácil ver que eso es cierto. En realidad, la conjetura de Hirsch es cierta para cualquier poliedro de dimensión tres (D = 3). Lo que pasa es que los matemáticos normalmente trabajamos con espacios de un número de dimensiones arbitrario. No sólo porque podemos y porque como científicos debemos entender esos espacios, sino porque esos espacios aparecen muchas veces en las aplicaciones. Algebraicamente, cada dimensión no es más que una variable que aparece en nuestro problema y, obviamente, en muchas aplicaciones tecnológicas y científicas el número de variables no es tres sino que puede ser miles o incluso millones. ¿En que consiste el algoritmo símplex? ¿Qué relación tiene con la conjetura de Hirsch? El algoritmo del símplex (o del símplice, como a mí me gusta más llamarlo aunque es menos habitual; creo que símplex es un anglicismo) es uno de los algoritmos más usados para resolver problemas de programación lineal; es decir, para buscar el valor óptimo de una función lineal cuando tenemos restricciones también lineales en los valores posibles de las variables. Por ejemplo, un problema de programación lineal podría ser encontrar el valor máximo que puede tomar la función 3 x – 5 y + 4 z en el cubo que he definido antes (1). El algoritmo del símplex resuelve estos problemas buscando primero un vértice cualquiera del poliedro definido por las desigualdades, y luego moviéndose de vértice a vértice a través de las aristas y buscando siempre ir a un vértice en el que el valor de la función a optimizar haya aumentado (como si estuviéramos escalando una montaña). Cuando lleguemos a un vértice desde el que ya no podemos subir más, la convexidad del poliedro nos garantiza que estamos en el óptimo. Está claro, por tanto, que la conjetura de Hirsch pone un límite al número de pasos que uno espera dar al aplicar el algoritmo del símplex. Si la conjetura fuera cierta, aunque uno tuviera muy mala suerte con el primer vértice encontrado, estaría seguro de poder llegar al óptimo en un número pequeño de pasos. Hay que decir que la programación lineal es uno de los problemas matemáticos con más aplicaciones en la industria, las finanzas, la logística, etc. Por ejemplo, el actual presidente de la Unión Matemática Internacional, el húngaro László Lovász, dijo en 1980: Si hiciéramos estadísticas sobre qué problema matemático está usando más tiempo de computación en este momento en el mundo (excluyendo problemas de manejo de bases de datos, como búsqueda u ordenación) la respuesta sería probablemente la programación lineal. Otro ejemplo es que en el año 2000 la revista Computing in Science and Engineering elaboró una lista de los algoritmos más relevantes del siglo XX y el del símplice quedó en el “top-ten”. ¿Por qué se afirma que no sabemos si es un algoritmo polinómico, en el sentido de la teoría de la complejidad? La teoría de la complejidad estudia cuántos pasos (en cierto modo, cuánto tiempo) va a tardar un algoritmo en darnos la respuesta a un problema. Por supuesto, es número depende del input concreto (en nuestro caso, el poliedro o sistema de ecuaciones concreto al que le queremos aplicar el algoritmo del símplice). Lo que intenta la teoría de la complejidad es predecir el número de pasos en función del tamaño del input (en nuestro caso, el número de ecuaciones y variables, y también lo grandes que sean los coeficientes de esas ecuaciones). O sea, en teoría de complejidad uno se pregunta: “Si le damos al algoritmo del símplice un input de tamaño, digamos K, ¿cuánto tardará el algoritmo en darnos la respuesta? ¿Tardará, más o menos, K 3 pasos, o 2k pasos, o…? Por supuesto, estoy simplificando porque la “complejidad” nunca va a venir dada por una expresión tan sencilla. Pero es que en realidad lo importante no es la expresión en sí sino si es una expresión polinómica o exponencial. Polinómica significa que lo que aparece en los exponentes es constante, independiente de K (como en K 3). Exponencial significa que el exponente depende de K(como en 2K). La importancia radica en que una función exponencial crece mucho más rápido que una polinómica. En la práctica, un algoritmo exponencial se considera “intratable” mientras que uno polinómico es “razonable”. Por ejemplo, si tomamos K=1000, tenemos que K 3 son 1000 millones (un 1 seguido de nueve ceros) mientras que 21000 es, más o menos, 1000100, o sea un 1 seguido de 300 ceros. 1000 millones de pasos puede parecernos un número muy grande, pero recordemos que un ordenador actual de, digamos, 2 Gigahercios, realiza 2000 millones de operaciones por segundo. Habría que ver cuántas “operaciones del procesador” son necesarias para cada “paso del algoritmo”, pero parece que 1000 millones de pasos no va a llevarnos demasiado tiempo. En cambio, el “1 seguido de 300 ceros” aunque le dividamos por los mil millones de operaciones por segundo nos da un “1 seguido de 291 ceros”. Ni el mismo Dios, si se me permite la expresión, podría esperar tanto tiempo. ¿Qué pasos se han dado en la demostración de la conjetura y en que consiste el Teorema de los d pasos? El Teorema de los d pasos, demostrado en 1967 por Klee y Walkup, nos dijo que para estudiar la conjetura de Hirsch bastaba con estudiar el caso particular en que N = 2D. Es decir, Klee y Walkup demostraron que si existía algún poliedro que violara la conjetura, entonces también habría alguno que la violara y en el que, además, N = 2D. Parte de mi demostración consiste en lo que llamo el “Teorema de los d pasos generalizado” que dice que si la conjetura de Hirsch es cierta, entonces también ha de ser cierta una afirmación un poco más manejable sobre ciertos poliedros a los que llamo husos. Después, construyo un huso concreto de dimensión cinco en el que esa afirmación no se cumple, lo cual implica que hay un poliedro en el que se viola la conjetura de Hirsch. (Aunque ya no de dimensión 5, en principio lo mejor que he conseguido es dimensión 43 aunque estoy trabajando en reducir ese número) ¿Qué importancia tiene encontrar un contraejemplo a la conjetura de Hirsch y qué perspectivas se abren para el desarrollo de la programación lineal? Mi refutación ha tenido cierta repercusión tanto en el mundo académico como en la prensa generalista por el número de años que la conjetura lleva abierta y por su relación con la programación lineal y el método del símplice. Pero no quiero engañar a nadie. El método del símplice funciona muy bien (por eso se usa!) y va a seguir funcionando bien. En la práctica, se comporta como un algoritmo no sólo polinómico sino incluso lineal (la función de complejidad no tiene ningún exponente, ni 3 , ni 2, ni 1,01). Lo que pasa es que no sabemos por qué funciona. La conjetura de Hirsch era una posible explicación y lo que mi contraejemplo significa es que debemos seguir buscando. ¿Por qué? Pues para “avanzar en el conocimiento”. Pero es que, además, si no sabemos por qué algo funciona malamente podremos mejorarlo, o arreglarlo si en algún momento deja de funcionar. Esto último, por cierto, es en mi opinión la raíz de nuestros problemas económicos. Hemos dejado pasar demasiado tiempo viendo (o pensando) que nuestra economía funcionaba pero sin preguntarnos por qué, y sin darnos cuenta de que lo que la hacía funcionar (básicamente, el flujo de dinero de Europa a España, y el endeudamiento creciente de familias, empresas e instituciones) era insostenible. En palabras de Radio Futura: “…pero no te has preguntado cuánto puede durar ir tirando de prestado y sin poder pagar. ¡Tú dónde vas!”. El 10 de Mayo de 2010 Francisco Santos Leal envió el siguiente resumen de su próxima conferencia al congreso The Mathematics of Klee and Grünbaum: 100 years in Seattle, anunciando que había encontrado un contraejemplo a la Conjetura de Hirsch: “He estado en Seattle sólo una vez, en enero de 2002, con motivo de una charla en la Universidad de Washington. Aunque Victor Klee ya estaba jubilado –tenía 76 años– vino al Departamento para charlar conmigo. Tuvimos una amena conversación en el transcurso de la cual me preguntó: ¿Por qué no intentas refutar la Conjetura de Hirsch? Más tarde descubrí que Klee formulaba la misma pregunta a mucha gente, incluyendo a todos sus alumnos, pero la pregunta y la forma en que me la planteó me hizo sentir especial en ese momento. Esta charla es la respuesta a esa pregunta. Describiré la construcción de una politopo de dimensión 43 con 86 facetas y diámetro mayor que 43. La prueba se basa en una generalización del teorema de los d-pasos de Klee y Walkup.” 1.- Para el lector interesado, el valor máximo resulta ser 7 y se obtiene cuando (x,y, z) = (1,0,1).