Charla 91: The Science of Brute Force


Date
2022-07-22

Conferencista: Jenny Paola Angarita Pasachoa, Estudiante de Matemáticas, Uptc

Fecha: Viernes 22 de julio de 2022, 3:00 p.m.

Lugar: C-119

Resumen: En la teoría de Ramsey, un problema matemático abierto desde hace mucho tiempo, es el problema de las ternas pitagóricas: considere todas las particiones del conjunto $\{1, 2, 3, \ldots \}$ de números naturales en un número finito de partes, la pregunta es si siempre al menos una parte contiene una terna pitagórica $(a, b, c)$, con $a^2 + b^2 = c^2$. Marijn Heule y Oliver Kullman demuestran en su artículo The Science of Brute Force, que cuando se divide en dos partes, la respuesta es afirmativa, y conjeturan que la respuesta es sí para cualquier tamaño finito de la partición. Para resolver el problema booleano de las ternas pitagóricas, basta con mostrar la existencia de un subconjunto de los números naturales, tal que cualquier partición de ese subconjunto en dos partes tiene una parte que contiene una terna pitagórica. Los autores se enfocaron en los subconjuntos $\{1,2,3,\ldots,n\}$, y determinaron usando el algoritmo de satisfacibilidad (SAT) que el n más pequeño para el que se cumple la propiedad es 7825. SAT es una herramienta lógica de la supercomputación que da lugar a una nueva era del algoritmo de la fuerza bruta.

Related