Problema del triplete booleano

El problema del triplete booleano es una cuestión relacionada con ternas pitagóricas, que se resolvió utilizando una prueba asistida por ordenador en mayo de 2016.^[1]

Este problema se enmarca en la teoría de Ramsey, y formula la pregunta de si es posible colorear cada uno de los enteros positivos, ya sea de color rojo o de color azul, de modo que ningún triplete pitagórico de los enteros a, b y c, que satisfaga la condición $a^{2}+b^{2}=c^{2}$ sean todos del mismo color. Por ejemplo, en el triplete pitagórico 3, 4 y 5 ( $3^{2}+4^{2}=5^{2}$ ), si 3 y 4 son de color rojo, entonces 5 debe ser de color azul.

Marijn Heule, Oliver Kullmann y Victor Marek investigaron el problema y demostraron que al menos existe un caso en el que tal coloración es imposible. Hasta el número 7824 es posible colorear los números de modo que todos los triples pitagóricos sean admisibles, pero la prueba muestra que dicho color no se puede extender para también colorear el número 7825. Se confirmó la afirmación del teorema, en el que se afirma que:

El conjunto {1, . . . , 7824} puede ser separado en dos partes, de forma que ninguna de las dos contenga una terna pitagórica, lo que es imposible para {1, . . . , 7825}.^[2]

Hay 2⁷⁸²⁵ coloraciones posibles para los números hasta 7825. Estas posibles coloraciones se redujeron lógica y algorítmicamente a alrededor de un trillón de (aún altamente complejos) casos, y se examinaron utilizando un resolucionador de problemas de satisfacibilidad booleana. El desarrollo de la prueba requirió aproximadamente 4 años de trabajo, así como dos días de cálculo en el superordenador Stampede del Texas Advanced Computing Center. Generó una prueba proposicional de 200 terabytes, que se comprimió a 68 gigabytes.

El documento que describe la prueba se publicó en arXiv el 3 de mayo de 2016,^[2] y fue aceptado para la conferencia SAT 2016, donde ganó el premio al mejor artículo.^[3]

En la década de 1980, el matemático Ronald Graham había ofrecido un premio de 100 dólares por la resolución del problema, otorgado a Marijn Heule en 2016.^[1]

Referencias

↑ ^a ^b Lamb, Evelyn (26 de mayo de 2016). «Two-hundred-terabyte maths proof is largest ever». Nature 534: 17-18. PMID 27251254. doi:10.1038/nature.2016.19990.
↑ ^a ^b Heule, Marijn J. H.; Kullmann, Oliver; Marek, Victor W. (3 de mayo de 2016). «Solving and Verifying the Boolean Pythagorean Triples problem via Cube-and-Conquer». Lecture Notes in Computer Science: 228-245. arXiv:1605.00723. doi:10.1007/978-3-319-40970-2_15.
↑ SAT 2016

Datos: Q25305453

[nature-1] Lamb, Evelyn (26 de mayo de 2016). «Two-hundred-terabyte maths proof is largest ever». Nature 534: 17-18. PMID 27251254. doi:10.1038/nature.2016.19990.

[arXiv-2] Heule, Marijn J. H.; Kullmann, Oliver; Marek, Victor W. (3 de mayo de 2016). «Solving and Verifying the Boolean Pythagorean Triples problem via Cube-and-Conquer». Lecture Notes in Computer Science: 228-245. arXiv:1605.00723. doi:10.1007/978-3-319-40970-2_15.

[3] SAT 2016

[1]

[2]

[3]