lunes, 4 de julio de 2016

SUPERORDENADOR RESUELVE EL PROBLEMA DE LAS TERNAS PITAGÓRICAS BOOLEANAS

MATEMÁTICAS
La demostración matemática más larga de la historia: 200 teraoctetos


Un superordenador resuelve el problema de las ternas pitagóricas booleanas. ¿Puede el resultado considerarse matemáticas?

Nature News

Tres teóricos de la computación presentaron hace unas semanas la demostración más larga de la historia de las matemáticas: un fichero de 200 teraoctetos (terabytes), un tamaño equiparable al de todos los textos digitalizados de la Biblioteca del Congreso estadounidense. Los investigadores han creado una versión comprimida de 68 gigaoctetos para que todo aquel que disponga de unas 30.000 horas de tiempo de procesador pueda descargarla, reconstruir la solución y verificarla. Sin embargo, ningún ser humano podrá jamás leerla ni comprobarla por sí mismo.

Hace tiempo que semejantes demostraciones por ordenador —demasiado largas para que un ser humano pueda verificarlas directamente— se han convertido en moneda común. Hoy los matemáticos están familiarizados con soluciones a problemas de combinatoria basadas en la verificación computarizada de un número descomunal de casos individuales. Con todo, 200 teraoctetos es algo «increíble», reconoce Ronald Graham, matemático de la Universidad de California en San Diego. Hasta ahora, se consideraba que el récord lo mantenía una demostración de 13 gigaoctetos presentada en 2014.

El rompecabezas cuya solución ha requerido 200 teraoctetos es el llamado «problema de las ternas pitagóricas booleanas», el cual llevaba décadas resistiéndose a los matemáticos. En los años ochenta, Graham ofreció un premio de 100 dólares a quien lograse resolverlo. Hace unos días, presentó el cheque correspondiente a Marijn Heule, investigador de la Universidad de Texas en Austin y uno de los tres autores de la prueba. En concreto, el problema consiste en averiguar si hay una manera de asignar uno de dos colores (digamos, rojo o azul) a cada número entero, de modo que no haya ninguna terna pitagórica (trío de números a, b y c que satisfagan el teorema de Pitágoras, a2 + b2 = c2) cuyos miembros sean todos del mismo color. Por ejemplo, una de tales ternas es la compuesta por los números 3, 4 y 5. Por tanto, si decidiésemos que el 3 y el 5 son de color azul, el 4 debería ser de color rojo.

En su trabajo, que fue subido el pasado 3 de mayo al repositorio de artículos científicos arXiv, Heule, Oliver Kullmann, de la Universidad de Swansea, y Victor Marek, de la Universidad de Kentucky en Lexington, han demostrado que hay muchas formas de colorear los números enteros hasta el 7824 de modo que nunca aparezcan ternas pitagóricas monocromáticas. Sin embargo, eso se torna imposible a partir del 7825. Aunque hay más de 102300 formas posibles de colorear los números enteros hasta el 7825, los autores sacaron partido de varias simetrías y técnicas de teoría de números para reducir el número de posibilidades que el ordenador tendría que comprobar a menos de un billón (1012). Después, 800 procesadores del superordenador Stampede, de la Universidad de Texas, trabajaron en paralelo durante dos días para verificarlas todas. Por último, los investigadores emplearon otro programa informático para comprobar la solución.


Una de las posibles formas de colorear de rojo o azul todos los números hasta el 7824, de modo que no haya ninguna terna pitagórica cuyos miembros sean todos del mismo color (las casillas blancas pueden ser de cualquier color; el eje vertical representa las centenas, y el horizontal, las correspondientes decenas y unidades). A partir del 7825, sin embargo, no resulta posible asignar uno de dos colores a los números enteros sin que aparezcan ternas pitagóricas monocromáticas. [Marijn Heule, Universidad de Texas en Austin: www.cs.utexas.edu/~marijn/ptn]

El problema de las ternas pitagóricas booleanas es una de las muchas cuestiones similares que aparecen en teoría de Ramsey, una rama de las matemáticas encargada de estudiar las propiedades que emergen en conjuntos con un gran número de elementos. Por ejemplo, los expertos creen que, si el problema permitiese emplear tres colores en lugar de solo dos, antes o después seguiría habiendo un número a partir del cual sería imposible evitar la aparición de una terna pitagórica monocromática. De hecho, se cree que lo mismo debería ocurrir para cualquier asignación de un número finito de colores. Pero, a menos que la técnica consistente en comprobar todas las posibilidades se vea simplificada gracias a algún gran avance en la comprensión del problema, toda demostración para el caso de más de dos colores probablemente ocuparía mucho más de 200 teraoctetos.

Kullman señala que, aunque el ordenador haya resuelto el problema de las ternas booleanas, la solución no permite entender por qué ocurre así, ni tampoco qué tiene de especial el número 7825. Su comentario trae a la cabeza una objeción filosófica que suele lanzarse contra este tipo de demostraciones efectuadas por un ordenador: si el trabajo de un matemático se interpreta como un esfuerzo por aumentar el entendimiento humano de las matemáticas —y no tanto como un intento de elaborar, sin más, largas listas de hechos—, una demostración basada en consideraciones teóricas debería considerarse superior a la verificación automatizada de todas las posibilidades.

Eso fue lo que acabó ocurriendo con la demostración de 13 gigaoctetos presentada en 2014, la cual resolvía un caso particular de una cuestión conocida como «problema de la discrepancia de Erdös». Un año después, el matemático de la Universidad de California Terence Tao resolvió el problema general a la antigua usanza: un logro mucho más satisfactorio.

Una versión del artículo técnico se encuentra disponible en el repositorio arXiv.

—Evelyn Lamb/Nature News

http://www.investigacionyciencia.es/noticias/la-demostracin-matemtica-ms-larga-de-la-historia-200-teraoctetos-14269?utm_source=boletin&utm_medium=email&utm_campaign=...+Y+m%C3%A1s+ciencia+-+Julio

0 comentarios:

Publicar un comentario

 
Design by Free WordPress Themes | Bloggerized by Lasantha - Premium Blogger Themes | JCPenney Coupons