En matemáticas, una conjetura es una afirmación que debe ser demostrada para ser irrefutable. Expresado de otro modo, se propone y posteriormente se comprueba. Una de estas conjeturas es la de Keller, cuyo enunciado dice que «un plano no puede ser cubierto totalmente con cuadrados idénticos sin solaparse sin que al menos dos de ellos compartan uno de sus lados». Hasta ahora se había demostrado para todos y cada uno de los números. Si bien, el 7 llevaba prácticamente un siglo desconcertando a los científicos. Pero uniendo matemáticas e informática, cuatro meses de frenética programación y 30 minutos de computación, por objetivo se ha conseguido ubicar la última pieza del rompecabezas: la demostración de la conjetura de Keller. El Equipo recurrió a un solucionador de SAT, -un programa de ordenador que USA lógica proposicional para resolver incidentes de satisfaciblidad (SAT)-, que ya sirvió para superar Múltiples desafíos matemáticos antiguos Tal como el problema de triples de Pitágoras y la Factorización de Schur. «El problema ha intrigado a muchas personas A lo largo de décadas, prácticamente un siglo», afirma en un comunicado el autor principal del hallazgo y profesor de ciencias de la computación, Marijn Heule. «Pero esto es verdaderamente una niña muestra de todo lo cual se puede hacer más tarde que Antes no era posible». La conjetura de las baldosas
La conjetura, planteada por el matemático alemán Eduard Ott-Heinrich Keller, debe ver con las baldosas. Específicamente, cómo cubrir un área con baldosas del mismo tamaño sin ningún espacio o superposición. La conjetura es que al menos dos de los mosaicos tendrán que compartir un borde y que esto es cierto para espacios de todas y cada una las dimensiones. Es sencilla demostrar que se cumple para los mosaicos bidimensionales y los cubos tridimensionales. En 1940, la conjetura había demostrado ser cierta para todas y cada una las dimensiones hasta seis. En 1990, Si es que bien, los matemáticos demostraron que no funciona en la dimensión 10 o bien superior. Fue luego en el instante la conjetura de Keller llamó la atención del maestro de Matemáticas John Mackey -y coautor del descubrimiento-, entonces Pupilo de la Universidad de Hawai. Estaba intrigado pues el problema podía traducirse, utilizando la teoría de grafos discretos, a una manera que los ordenadores pudieran explorar. En esta forma, llamada gráfica de Keller, los investigadores podrían buscar «camarillas», subconjuntos de elementos que se conectan sin compartir una hacia, refutando Así la conjetura. En 2002, Mackey logró detectar una camarilla en la dimensión ocho. Al hacerlo, probó que la conjetura falla en esa dimensión y, por extensión, en la dimensión nueve. No obstante la siete se quedó sin contestación. Cuando Heule alcanzó a la Universidad de Texas el año pasado, ya había usado el solucionador SAT para resolver los incidentes matemáticos pendientes. Un solucionador de SAT requiere estructurar el problema usando una fórmula proposicional (A o no B) y (B o bien C), etc., a fin de que el solucionador pueda investigar todas y cada una y cada una de las variables posibles para combinaciones que satisfagan todas y cada una las condiciones. «Hay muchas formas de hacer estas traducciones, y la calidad de la traducción, Por lo general, hace o rompe su capacidad para resolver el problema», dice Heule. Con 15 años de experiencia, Heule es experto en ejecutar estas traducciones. Uno de los objetivos de su investigación es desarrollar un razonamiento automatizado para que esta traducción se pueda realizar automáticamente, permitiendo que más y más personas utilicen estas herramientas en sus inconvenientes. Reducir las posibilidades a tan Sólo mil millones
Incluso con una traducción de alta calidad, la cantidad de combinaciones a verificar en la dimensión siete era demasiado grande-un número con 324 dígitos- con una solución que no se veía por ninguna parte, incluso con una supercomputadora. Pero Heule y los demás aplicaron una serie de trucos para reducir el tamaño del problema. Por servirnos de un ejemplo, si una configuración de información resultó inviable, podrían rechazar automáticamente otras combinaciones que se basaran en ella. Y dado que muchos de los información eran simétricos, el programa podía descartar imágenes espejo de una configuración si es que concurria a un callejón sin salida en una predisposición. Usando estas técnicas, redujeron su busca a más o bien menos 1.000 millones de configuraciones. Un número que, No obstante pueda parecer muy grande, puede ser procesado por los nuevos ordenadores. Cuando ejecutaron su código en un Sólo conjunto de 40 computadoras, Por último tuvieron una respuesta: la conjetura es cierta en la dimensión siete. «Me alegré mucho en el instante lo resolvimos, Sin embargo acto seguido A mí me entristeció un tanto que el problema desapareciera», asevera Mackey. «Pero luego A mí me sentí feliz nuevamente. Solo hay un sentimiento de satisfacción». «La razón por la que lo logramos es que John tiene décadas de experiencia y conocimiento de este problema y pudimos transformarlo en una búsqueda generada por computadora», asegura A su vez Heule. Aplicaciones prácticas y nuevos retos
Resolver la conjetura de Keller tiene aplicaciones prácticas: esas «camarillas» son útiles para generar códigos no lineales que pueden acelerar la transmisión de datos. Por tanto, el solucionador SAT se puede utilizar para detectar códigos no lineales de mayor dimensión de lo cual era posible anteriormente. Heule propuso recientemente usar el solucionador SAT para abordar un problema matemático aún más famoso: la conjetura de Collatz. En este problema, la idea es elegir cualquier número entero positivo y dividir por 2 si es que es un número par o multiplicar por 3 y sumar 1 si es un número impar. Acto seguido aplique exactamente las mismas reglas al número resultante y a cada resultado sucesivo. La conjetura es que el resultado final Siempre y en toda circunstancia y en toda circunstancia será 1. Resolver Collatz con el solucionador SAT «es una posibilidad remota», reconoce Heule. No obstante es una meta a la que aspira.