Investigadores demuestran equivalencia de teoremas complejos con matemática inversa

La matemática inversa ha permitido probar que teoremas aparentemente distintos en teoría de la complejidad son lógicamente equivalentes. Este método metamatématico intercambia axiomas por teoremas para explorar los fundamentos de la dificultad computacional.

Un enfoque invertido para problemas difíciles

Investigadores en teoría de la complejidad computacional llevan décadas intentando demostrar por qué problemas como el del viajante de comercio son inherentemente difíciles. La metatemática analiza el proceso de demostración cambiando los axiomas de partida. En un artículo de 2024, Lijie Chen, Jiatu Li e Igor Oliveira aplicaron la matemática inversa, sustituyendo un teorema por un axioma y probando luego ese axioma.

El principio del palomar como pieza clave

Chen partió del problema de la igualdad en complejidad de comunicación, cuya cota inferior se demuestra con el principio del palomar. Trabajando con el sistema axiomático PV1, Chen y Li demostraron en diciembre de 2022 que ambos enunciados son equivalentes dentro de ese marco lógico. Esta equivalencia se extendió después a otros teoremas.

Una red inesperada de conexiones

El equipo descubrió una equivalencia sorprendente entre el principio del palomar y la cota inferior para reconocer palíndromos en una máquina de Turing de una cinta. Marco Carmosino, de IBM, calificó este último teorema de «clásico». La conexión es notable porque el principio del palomar es un enunciado sobre conteo, mientras que la cota del palíndromo es específica de un modelo de computación.

Límites y repercusión del hallazgo

La red de equivalencias ayuda a iluminar los límites del sistema PV1. Dado que el principio del palomar probablemente no puede probarse solo con los axiomas de PV1, los teoremas equivalentes tampoco. Ján Pich, de Oxford, ve belleza en el resultado pero señala que el método es más útil para conexiones entre teoremas ya probados.

Antecedentes: La búsqueda de fundamentos

Durante más de 50 años, los investigadores han intentado convertir afirmaciones intuitivas sobre la dificultad de problemas en teoremas matemáticos sólidos, con éxito limitado. El trabajo en metatemática busca respuestas rigurosas a por qué no han tenido éxito esas demostraciones, analizando los propios fundamentos de la prueba matemática.

Cierre: Abriendo un nuevo camino

Este enfoque sugiere que las cotas inferiores de complejidad son más fundamentales de lo que parecen. Aunque entender el territorio inexplorado de lo no demostrado sigue siendo un objetivo lejano, el método atrae a nuevos investigadores. Jiatu Li ha escrito una guía de 140 páginas, señalando un interés creciente en la metatemática para desbloquear problemas estancados.