10 avances en matemáticas e informática teórica, explicados de forma sencilla

Las matemáticas y la informática teórica rara vez son noticia de portada como un nuevo teléfono inteligente o un fallo judicial, pero un puñado de resultados en estos campos han transformado silenciosamente lo que pueden hacer los ordenadores, lo que puede garantizar el cifrado y lo que se considera un problema resuelto. Estos son diez de los más significativos, elegidos por cuánto cambiaron el campo a su alrededor y no solo por su dificultad técnica.

El último teorema de Fermat, que sostiene que ningún trío de números enteros positivos puede satisfacer cierta ecuación sencilla una vez que el exponente es mayor que dos, quedó sin demostrar durante unos 350 años después de que el matemático del siglo XVII Pierre de Fermat afirmara tener una prueba que nunca escribió. El matemático británico Andrew Wiles finalmente lo demostró en 1994, en una prueba de cientos de páginas que recurría a técnicas muy alejadas de lo que Fermat podría haber conocido, cerrando una de las preguntas abiertas más famosas de las matemáticas.

La conjetura de Poincaré, un enunciado sobre la forma de los espacios tridimensionales planteado por primera vez en 1904, permaneció sin resolver hasta que el matemático ruso Grigori Perelman publicó una demostración en 2002 y 2003 utilizando una técnica llamada flujo de Ricci, que suaviza las irregularidades de las formas geométricas con el tiempo. Sigue siendo, hasta la fecha, el único de los siete Problemas del Milenio, una lista de grandes preguntas sin resolver con una recompensa de un millón de dólares cada una, que ha sido resuelto; Perelman rechazó tanto el dinero del premio como la Medalla Fields.

En 1976, el teorema de los cuatro colores, que sostiene que cualquier mapa puede colorearse usando solo cuatro colores de modo que dos regiones adyacentes nunca compartan color, se convirtió en el primer gran teorema matemático demostrado con ayuda sustancial de un ordenador, cuando Kenneth Appel y Wolfgang Haken usaron un programa para verificar miles de configuraciones de mapas individuales que habría sido poco práctico comprobar a mano. El resultado desató un debate de larga duración sobre si una prueba demasiado extensa para que un humano la revise línea por línea sigue contando como una prueba.

El avance sobre la conjetura de los primos gemelos, la idea aún no demostrada de que existen infinitos pares de números primos que difieren exactamente en dos, dio un paso importante en 2013, cuando Yitang Zhang, entonces un profesor relativamente desconocido, demostró que existen infinitos pares de primos que difieren en menos de 70 millones. Un rápido esfuerzo colaborativo que involucró al matemático James Maynard y a otros redujo esa brecha a 246, aunque cerrarla hasta el valor conjeturado de dos sigue sin resolverse.

El algoritmo de Peter Shor, de 1994, demostró que un ordenador cuántico suficientemente potente podría factorizar números grandes exponencialmente más rápido que cualquier método conocido en un ordenador clásico, un resultado enormemente relevante porque gran parte del cifrado moderno, incluidos los sistemas que protegen la banca en línea y las comunicaciones, se basa en que factorizar números grandes sea computacionalmente inviable. El algoritmo de Shor sigue siendo una razón central por la que gobiernos y empresas compiten por desarrollar tanto ordenadores cuánticos como cifrado resistente a la computación cuántica.

El teorema PCP, desarrollado a principios de la década de 1990 por un grupo de científicos de la computación teórica, demostró que toda demostración matemática puede reescribirse en una forma que un verificador puede comprobar examinando solo una pequeña fracción elegida al azar, detectando aun así cualquier error con alta probabilidad. El resultado transformó el estudio de los algoritmos de aproximación, proporcionando una forma rigurosa de demostrar que ciertos problemas de optimización no pueden aproximarse eficientemente, y no solo que nadie había encontrado todavía la manera de hacerlo.

Determinar si dos grafos grandes y complejos son estructuralmente idénticos, conocido como el problema del isomorfismo de grafos, se había resistido durante décadas a algoritmos generales eficientes. En 2015, el matemático László Babai anunció un algoritmo de tiempo cuasi-polinómico para el problema, una mejora significativa respecto a los enfoques anteriores y un avance notable en la teoría de la complejidad computacional, un área que se ocupa de clasificar cuán difíciles son los distintos problemas de cálculo.

La cuestión de cómo empaquetar esferas de la forma más densa posible en un número dado de dimensiones solo se había resuelto para un puñado de dimensiones bajas hasta que la matemática Maryna Viazovska demostró el empaquetamiento óptimo para el espacio de ocho dimensiones en 2016 y, poco después, trabajando con varios colaboradores, extendió la técnica para resolver el mismo problema en 24 dimensiones, resultados que también tuvieron implicaciones para la teoría de la información y los códigos de corrección de errores.

El problema de discrepancia de Erdős, planteado por el prolífico matemático Paul Erdős, se refería a cuán desigualmente podía distribuirse una secuencia de valores más uno y menos uno. Un caso especial se verificó en 2014 utilizando un resolutor SAT informático, en una demostración tan extensa que requería unos 13 gigabytes para almacenarse, en su momento una de las demostraciones matemáticas más grandes jamás producidas. Al año siguiente, Terence Tao demostró la conjetura completa y general utilizando métodos analíticos más tradicionales, resolviendo un problema que había permanecido abierto desde la década de 1930.

Lo que une a estos resultados, afirman los matemáticos, es menos su temática que lo que revelan sobre cómo ocurre el progreso matemático: a veces a través de décadas de refinamiento incremental por parte de muchos investigadores, como con las brechas entre primos, y a veces a través de una única idea que replantea todo un problema, como con el flujo de Ricci o el teorema PCP, con los ordenadores desempeñando un papel cada vez mayor, ya sea como herramienta de verificación o, más recientemente, como colaborador de investigación por derecho propio.