El uso de técnicas metamatemáticas ha permitido demostrar que ciertos teoremas que parecen distintos son, en realidad, lógicamente equivalentes.

Un artículo de Ben Brubaker. Historia original reimpresa con permiso de Quanta Magazine, una publicación editorialmente independiente respaldada por la Fundación Simons.

En lo que respecta a los problemas difíciles, los científicos de la computación parecen estar atascados. Consideremos, por ejemplo, el famoso problema de encontrar la ruta circular más corta que pase exactamente una vez por cada ciudad de un mapa. Todos los métodos conocidos para resolver este «problema del viajante de comercio» son desesperadamente lentos cuando el mapa contiene muchas ciudades, y los investigadores sospechan que no existe una forma de hacerlo mejor. Sin embargo, nadie sabe cómo demostrarlo.

Desde hace más de 50 años, los investigadores en teoría de la complejidad computacional han intentado convertir afirmaciones intuitivas como «el problema del viajante de comercio es difícil» en teoremas matemáticos irrefutables, con escaso éxito. Cada vez más, también buscan respuestas rigurosas a una pregunta relacionada y más difusa: ¿por qué no han tenido éxito sus demostraciones?

Este trabajo, que trata el propio proceso de demostración matemática como un objeto de análisis matemático, forma parte de un campo conocido por su dificultad: la metamatemática. Los metamatemáticos suelen examinar los supuestos básicos, o axiomas, que sirven como punto de partida de todas las demostraciones. Modifican estos axiomas iniciales y estudian cómo los cambios afectan a los teoremas que pueden demostrarse. Cuando se aplica la metamatemática al estudio de la teoría de la complejidad, el objetivo es determinar qué pueden y qué no pueden demostrar distintos conjuntos de axiomas sobre la dificultad computacional. De este modo, los investigadores esperan comprender por qué sus intentos de demostrar que ciertos problemas son difíciles no han prosperado.

En un artículo publicado el año pasado, tres investigadores adoptaron un enfoque distinto. Invirtieron el método que los matemáticos han utilizado durante milenios: en lugar de partir de un conjunto estándar de axiomas para demostrar un teorema, sustituyeron uno de los axiomas por un teorema y demostraron ese axioma. Mediante este enfoque, conocido como matemática inversa, demostraron que muchos teoremas distintos de la teoría de la complejidad son, en realidad, equivalentes.

«Me sorprendió que consiguieran avanzar tanto», afirma Marco Carmosino, teórico de la complejidad en IBM. «La gente va a mirar esto y va a decir: “Esto es lo que me hizo entrar en la metamatemática”».

Demostraciones con palomas

La historia del artículo sobre matemática inversa comenzó en el verano de 2022, cuando Lijie Chen, teórico de la complejidad y actualmente profesor en la Universidad de California en Berkeley, estaba terminando su doctorado. Con más tiempo libre del habitual, decidió dedicar unos meses a estudiar metamatemática.

«Como me estaba graduando, no tenía mucho trabajo de investigación que hacer», explica Chen. «Pensé que debía aprender algo nuevo».

Durante sus lecturas, Chen empezó a reflexionar sobre una rama de la teoría de la complejidad llamada complejidad de la comunicación, que estudia cuánta información deben intercambiar dos o más personas para realizar determinadas tareas. Uno de los problemas más sencillos de este campo, conocido como el «problema de la igualdad», se asemeja a un juego colaborativo. Dos jugadores comienzan con cadenas independientes de ceros y unos, es decir, de bits. Su objetivo es utilizar la menor cantidad posible de comunicación para determinar si ambas cadenas son idénticas. La estrategia más simple consiste en que uno de los jugadores envíe la cadena completa para que el otro la compruebe. La pregunta es si existe alguna forma más eficiente de proceder.

Los teóricos de la complejidad demostraron hace décadas que la respuesta es negativa. Para resolver el problema de la igualdad, los jugadores deben enviar, como mínimo, un número de bits igual a la longitud de la cadena completa. Esta longitud constituye una cota inferior de la cantidad de comunicación necesaria.

Chen no se centraba tanto en la cota inferior del problema en sí como en la forma en que se había demostrado. Todas las demostraciones conocidas dependen de un teorema sencillo llamado principio del palomar, que establece que si se colocan más palomas que palomares, al menos un palomar contendrá más de una paloma. Aunque pueda parecer evidente, este principio es una herramienta muy poderosa en la teoría de la complejidad y en otros ámbitos de las matemáticas.

Chen encontró una pista sugerente: la relación entre el problema de la igualdad y el principio del palomar podría funcionar también en sentido inverso. Es sencillo utilizar el principio del palomar para demostrar la cota inferior del problema de la igualdad. La cuestión era si esa cota inferior podría utilizarse, a su vez, para demostrar el principio del palomar.

Una igualdad inquietante

Chen comentó su idea con Jiatu Li, que en aquel momento era estudiante de grado en la Universidad de Tsinghua y con quien había colaborado recientemente en otro artículo. Para formalizar la conexión, necesitaban elegir un conjunto de axiomas con el que trabajar. En metamatemática es habitual utilizar axiomas más restrictivos que los convencionales, ya que estos sistemas más débiles permiten identificar con mayor precisión las relaciones entre distintos teoremas. Chen y Li optaron por un conjunto de axiomas muy utilizado llamado PV1. PV1 es lo suficientemente potente como para demostrar por sí solo algunos teoremas importantes de la teoría de la complejidad computacional. Si se añade una versión concreta del principio del palomar como axioma adicional, también permite demostrar la cota inferior del problema de la igualdad. En diciembre de 2022, Li y Chen demostraron formalmente que, como Chen había sospechado, la demostración también funciona intercambiando el papel de ambos teoremas.

Que la cota inferior del problema de la igualdad pueda demostrarse a partir del principio del palomar, y viceversa, implica que, dentro del marco lógico de PV1, ambos teoremas son equivalentes. Cuando Li y Chen comentaron el resultado con Igor Oliveira, teórico de la complejidad en la Universidad de Warwick, los tres se dieron cuenta de que este enfoque de matemática inversa podría aplicarse también a teoremas de otras áreas de la teoría de la complejidad. En los meses siguientes, demostraron de forma sistemática equivalencias entre muchos otros resultados.

«Al principio solo teníamos dos resultados equivalentes», explica Chen. «Ahora tenemos toda una red de ellos».

La conexión más llamativa relaciona la misma versión del principio del palomar con uno de los primeros teoremas que suelen estudiarse en los cursos introductorios de teoría de la complejidad. Este «clásico imprescindible», en palabras de Carmosino, establece una cota inferior sobre el tiempo necesario para que un tipo de ordenador teórico —una máquina de Turing de una sola cinta— determine si una cadena de ceros y unos es un palíndromo, es decir, si se lee igual de izquierda a derecha que de derecha a izquierda. Mediante la matemática inversa, Li, Chen y Oliveira demostraron que, dentro de PV1, este teorema es equivalente al principio del palomar.

«Si alguien me lo hubiera dicho, no lo habría creído», reconoció Chen. «Suena completamente absurdo».

Esta equivalencia resulta sorprendente porque ambos teoremas parecen, a primera vista, muy distintos. El principio del palomar no está vinculado de forma intrínseca al cálculo: es una afirmación elemental sobre conteo. La cota inferior para palíndromos, en cambio, se refiere a un modelo concreto de computación. El nuevo resultado sugiere que teoremas aparentemente específicos tienen un alcance mucho más general de lo que cabría esperar.

«Indica que estas cotas inferiores de complejidad que queremos comprender son mucho más fundamentales», señaló Oliveira.

Territorio inexplorado

Esta red de equivalencias también ha permitido clarificar los límites de PV1. Los investigadores ya tenían motivos para pensar que el principio del palomar no puede demostrarse a partir de los axiomas de PV1 por sí solos, por lo que los resultados de Li, Chen y Oliveira implican que los demás teoremas equivalentes probablemente tampoco sean demostrables en ese sistema.

«Me parece precioso», afirma Ján Pich, teórico de la complejidad en la Universidad de Oxford, que en 2014 obtuvo un resultado importante sobre la potencia de PV1. No obstante, advirtió que el enfoque de la matemática inversa puede resultar especialmente útil para revelar nuevas conexiones entre teoremas ya conocidos. «No nos dice gran cosa, hasta donde podemos afirmar, sobre la complejidad de enunciados que aún no sabemos cómo demostrar».

Comprender ese territorio inexplorado sigue siendo un objetivo lejano para los investigadores en metamatemática. Sin embargo, esto no ha reducido el entusiasmo de Li por el campo. Inició sus estudios de posgrado en el Instituto Tecnológico de Massachusetts en 2023 y recientemente escribió una guía de 140 páginas sobre metamatemática dirigida a teóricos de la complejidad. Es un ejemplo de una tendencia más amplia: tras décadas de relativa marginalidad, la metamatemática está atrayendo cada vez más atención por parte de una comunidad más amplia de investigadores, que aportan nuevas perspectivas al área.

«La gente está cansada de estar bloqueada», concluye Carmosino. «Es el momento de dar un paso atrás y trabajar en los fundamentos».

El artículo original, ‘Reverse Mathematics’ Illuminates Why Hard Problems Are Hard, se publicó el 1 de diciembre de 2025 en Quanta Magazine.

Traducido por César Tomé López