Dos demostraciones de procedencia inusual para un mismo problema [Maciej Rebisz para Quanta Magazine.].
El 16 de septiembre de 2011, un aficionado al anime subió al foro o tablón de imágenes en Internet 4chan una pregunta de matemáticas relativa a la serie de televisión de culto La melancolía de Haruhi Suzumiya. La primera temporada de la serie, en la que hay viajes por el tiempo, no se emitió originalmente en orden cronológico; una emisión posterior y una versión en DVD reordenaron los episodios. Los seguidores de la serie debatieron en Internet acerca de cuál era el mejor orden de los episodios; el mensaje colgado en 4chan se preguntaba lo siguiente: si los espectadores quisiesen ver la serie ordenada de todas las maneras posibles, ¿cuál sería la lista con menos episodios que tendrían que ver?
En menos de una hora, alguien, de forma anónima, ofreció una respuesta. No se trataba de una solución completa, sino de una cota inferior del número de episodios requerido. El argumento, válido para series con cualquier número de episodios, mostraba que para los 14 de la primera temporada de Haruhi los espectadores tendrían que ver al menos 93.844.313.611 episodios para que no se les escapase ninguna ordenación. «Por favor, compruébala [la prueba] por si hubiese algún resquicio que he pasado por alto», escribía el anónimo autor.
La prueba les pasó inadvertida a los matemáticos durante siete años; parece que solo un matemático profesional la vio en su momento, pero no la comprobó meticulosamente. Pero la historia sufrió un giro singular el mes pasado, cuando el novelista australiano de ciencia ficción Greg Egan demostró una nueva cota superior del número de episodios requerido. El descubrimiento de Egan renovó el interés por el problema y llamó la atención sobre la cota inferior subida anónimamente a la Red en 2011. A ambas pruebas se las considera ahora un avance significativo en un problema que los matemáticos llevan estudiando 25 años.
Los matemáticos verificaron enseguida la cota superior de Egan, que, como la inferior, es válida para series de cualquier longitud. Entonces, Robin Houston, matemático de Kiln, una empresa dedicada a la visualización de datos, y Jay Pantone, de la Universidad Marquette, de Milwaukee, verificaron, cada uno por su lado, el trabajo del anónimo corresponsal de 4chan. «Costó mucho trabajo averiguar si era correcta o no», dice Pantone, ya que las ideas clave no estaban demasiado bien expresadas.
Ahora, Houston y Pantone, a los que se ha unido Vince Vatter, de la Universidad de Florida en Gainesville, han escrito un artículo formal. En él, ponen como primer autor al «corresponsal anónimo de 4chan». «Es bien extraño que una prueba tan elegante de algo hasta entonces desconocido se subiese a un sitio tan improbable».
Ciudades de permutaciones
Si una serie de televisión tuviese solo tres episodios, habría seis posibles formas de verlos: 123, 132, 213, 231, 312 y 321. Se pueden poner estas seis secuencias una tras y otra para obtener una lista de 18 episodios que incluye todas las ordenaciones posibles, pero hay una forma mucho más eficiente de hacerlo: 123121321. Una secuencia como esta, que contiene cada posible reordenación (o permutación) de una colección de n símbolos, recibe el nombre de «superpermutación».
En 1993, Daniel Ashlock y Jenett Tillotson observaron que si uno se fija en la superpermutaciones más cortas para diferentes valores n enseguida parece emerger una pauta con factoriales, los números, simbolizados de la forma n!, iguales a la multiplicación de todos los números hasta n (por ejemplo, 4! = 4 x 3 x 2 x 1).
Si la serie solo tiene un episodio, la supermutación más corta tendrá una longitud de 1!. Con tres episodios (el ejemplo de más arriba), la longitud resulta ser de 3! + 2! + 1!, y con cuatro (1234123142312431213421322413214321) es 4! + 3! + 2! + 1!. La regla factorial de las superpermutaciones se convirtió en una idea comúnmente aceptada pese a que no se había podido probarla para todos los valores de n; luego, se confirmaría para n = 5.
En 2014, Houston sorprendió a los matemáticos al mostrar que para n = 6 la pauta deja de ser válida. La regla factorial predice que para ver seis episodios ordenados de todas las formas posibles se necesitarían 873 episodios, pero Houston encontró una forma de hacerlo con 872. Y como hay una forma sencilla de convertir una corta superpermutación de n símbolos en una de n + 1, el ejemplo de Houston significa que la regla factorial falla también para todos los valores de n mayores que 6.
La construcción de Houston se basa en convertir el problema de la superpermutación en el famoso problema del viajante, que busca la ruta más corta a través de una serie de ciudades. Más en concreto, las superpermutaciones están relacionadas con el problema asimétrico del viajante, en el que cada camino entre dos ciudades tiene un coste (no necesariamente el mismo en ambas direcciones); lo que se busca es la ruta menos cara a través de todas las ciudades.
La conversión es simple: tómese a cada permutación como si fuese una «ciudad» e imagínese un camino de cada permutación a las otras. En el problema de las superpermutaciones queremos dar con la secuencia más corta posible de dígitos que sea una lista de todas las permutaciones, así que el objetivo consiste en viajar a través de todas las permutaciones de una forma que añada tan pocos dígitos a la permutación de partida como sea posible. Establecemos que el coste de cada camino es sencillamente el número de dígitos que tenemos que añadir al final de la primera permutación para obtener la segunda. Con n = 3, por ejemplo, el camino de 231 a 312 cuesta 1$, ya que solo tenemos que añadir un 2 al final de 231 para obtener 312, mientras que el camino de 231 a 132 cuesta 2$, ya que hay que añadir un 32. Con esta forma de verlo, la ruta menos cara entre las ciudades se corresponde directamente con la supermutación más corta.
Esta conversión le permitía a Houston aplicar los potentes algoritmos del viajante al problema de las superpermutaciones. El problema del viajante es famoso por ser un problema NP duro; no se conocen algoritmos eficientes que lo resuelvan en todos los casos. Pero sí hay algoritmos que pueden resolver algunos casos eficientemente y otros que producen buenas aproximaciones. Houston se valió de uno de los últimos para generar su superpermutación de 872 dígitos.
Como solo generó una solución aproximada, podría no ser la mejor superpermutación. Se está realizando ahora una simulación por ordenador gigantesca en pos de la superpermutación de seis símbolos más corta, dice Pantone. «Sabemos que nuestra búsqueda terminará en un tiempo finito, pero no sabemos si se tratará de una semana o de un millón de años», afirma. «No hay una barra del tanto por ciento realizado».
En el orden equivocado
Para cuando Houston hizo su trabajo, el mensaje anónimo de 4chan llevaba en su rincón de Internet tres años. Un matemático, Nathaniel Johnston, de la Universidad Mount Allison, vio una copia en otro sitio de la Red unos días después de que fuese colgado, no porque fuese aficionado al anime, sino porque hizo una búsqueda en Google con palabras relacionadas con las superpermutaciones.
Johnston leyó el argumento y le pareció verosímil, pero no se esforzó en comprobarlo a fondo. Por entonces, los matemáticos creían que la formula de los factoriales para las superpermutaciones era probablemente correcta, y cuando se cree que se tiene la respuesta correcta de un problema una cota inferior no es muy interesante. En otras palabras, los episodios de la investigación de las superpermutaciones se estaban representado desordenadamente.
Johnston mencionó más tarde la cota inferior en un par de sitios de la Red, pero «no creó que nadie hiciese mucho caso», dice.
Pero el 26 de septiembre de este año el matemático John Baez, de la Universidad de California en Riverside, publicaba en Twitter un mensaje sobre el hallazgo de Houston en 2014 dentro de una serie de tuits sobre pautas matemáticas aparentes que fallan. Su tuit captó la atención de Egan, que se licenció en matemáticas hace décadas, antes de emprender su premiada carrera de escritor de ciencia ficción (en una feliz coincidencia, la novela que le abrió paso, en 1994, se llama Ciudad de permutaciones). «Nunca he dejado de interesarme por [las matemáticas]», explica en un mensaje de correo electrónico.
Egan se preguntó si era posible construir superpermutaciones aún más cortas que la de Houston. Rastreó la literatura en busca de artículos que tratasen de la construcción de caminos cortos a través de redes de permutaciones, y tras unas semanas encontró justo lo que necesitaba. En un día o dos dio con una nueva cota superior de la longitud de la superpermutación más corta de n símbolos: n! + (n-1)! + (n-2)! + (n-3)! + n – 3. Se parece a la vieja fórmula factorial, pero quitándole muchos términos.
«Ha machacado por completo la cota superior [anterior]», dice Houston.
La cota inferior colgada en 4chen estaba llamativamente cerca de la nueva cota superior: n! + (n-1)! + (n-2)! + n – 3. Cuando el resultado de Egan se hizo público, Johnston recordó a otros matemáticos la prueba anónima en 4chan, y Houston y Pantone demostraron enseguida que era correcta. En el trabajo de Houston, las nuevas cotas inferior y superior les vienen a las superpermutaciones desde el problema del viajante: la cota inferior muestra que una ruta a través de todas las ciudades debe realizar algún número mínimo de caminos que cuesten más de 1$, mientras que la superior construye una ruta concreta para cada n que solo usa conexiones de 1$ y 2$.
Los investigadores intentan ahora juntar la cota inferior y la superior para encontrar una sola fórmula que resuelva el problema de las superpermutaciones. «Es probable que se llegue a resolver por completo este problema», predice Baez. «Tiene buenas pintas ahora».
Para los seguidores de Haruhi, la construcción de Egan da instrucciones explícitas sobre cómo ver todas las posibles ordenaciones de la primera temporada con solo 93.924.230.411 episodios. Los espectadores podrían empezar su atracón de episodios inmediatamente, o esperar a ver si los matemáticos rebajan el número. La cota inferior del mensaje anónimo demuestra que esa rebaja no podría ahorrar más de 40 millones de episodios, pero basta para arrancar con buen pie con la segunda temporada.
Erica Klarreich / Quanta Magazine
Artículo traducido por Investigación y Ciencia con permiso de QuantaMagazine.org, una publicación independiente promovida por la Fundación Simons para potenciar la comprensión de la ciencia.
Referencia: «A lower bound on the length of the shortest superpattern», de Anonymous 4chan Poster, Robin Houston, Jay Pantone y Vince Vatter en Google Documents.
