Un matemático ha resuelto un problema de 30 años en el límite entre las matemáticas y la informática. Utilizó una prueba innovadora y elegante que hace que sus colegas se maravillen de su simplicidad.
Hao Huang, profesor asistente de matemáticas en la Universidad de Emory en Atlanta, demostró una idea matemática llamada conjetura de sensibilidad, que, en términos increíblemente aproximados, afirma cuánto puede cambiar la entrada a una función sin cambiar la salida (esto es su sensibilidad)
En las décadas transcurridas desde que los matemáticos propusieron por primera vez la conjetura de la sensibilidad (sin demostrarlo), los científicos teóricos de la computación se dieron cuenta de que tiene enormes implicaciones para determinar las formas más eficientes de procesar la información.
Lo notable de la prueba de Huang, según otros expertos en el campo, no es solo que Huang lo logró, sino también la forma elegante y directa en que lo hizo. Su prueba no ha sido oficialmente revisada por pares ni publicada en ninguna revista de matemáticas. Pero poco después de que Huang lo pusiera en línea el 1 de julio, sus colegas lo aceptaron rápidamente como un hecho.
"Cada vez que hay un anuncio como este", escribió el científico teórico de la computación de la Universidad de Texas en Austin, Scott Aaronson, en su blog, "~ 99% de las veces la prueba es incorrecta o, en cualquier caso, es demasiado complicado para los extraños evaluarla". rápidamente. Este es uno de los casos restantes del 1%. Estoy bastante seguro de que la prueba es correcta. ¿Por qué? Porque lo leí y lo entendí. Me tomó alrededor de media hora ".
Ryan O'Donnell, profesor de ciencias de la computación que estudia teoría de números en la Universidad Carnegie Mellon de Pittsburgh, señaló que la prueba de Huang se puede resumir en un solo tuit:
¿Qué probó realmente Huang?
En aras de la simplicidad, imagine un cubo 3D con lados de 1 unidad de longitud. Si coloca este cubo en un sistema de coordenadas 3D (lo que significa que tiene medidas en tres direcciones), una esquina tendría las coordenadas (0,0,0), la que está al lado podría ser (1,0,0), el uno arriba podría ser (0,1,0) y así sucesivamente. Puede tomar la mitad de las esquinas (cuatro esquinas) sin tener ningún par de vecinos: (0,0,0), (1,1,0), (1,0,1) y (0,1,1) no son t vecinos. Puede mostrar esto mirando el cubo, pero también lo sabemos porque todos ellos son diferentes en más de una coordenada.
La conjetura de la sensibilidad se trata de encontrar cuántos vecinos tienes cuando tomas más de la mitad de las esquinas de un cubo de mayor dimensión, o un hipercubo, dijo el matemático de la Universidad Hebrea Gil Kalai. Puedes escribir las coordenadas del hipercubo como cadenas de 1s y 0s, donde el número de dimensiones es la longitud de la cadena, dijo Kalai a Live Science. Para un hipercubo 4D, por ejemplo, hay 16 puntos diferentes, lo que significa 16 cadenas diferentes de 1s y 0s que tienen cuatro dígitos de largo.
Ahora elija la mitad más 1 puntos individuales en el hipercubo (para un hipercubo 4D, eso significa elegir nueve, u 8 + 1, puntos diferentes de un total de 16).
De este conjunto más pequeño, encuentre el punto con la mayoría de los vecinos: ¿cuál es el mínimo ¿Cuántos vecinos puede tener? (Los vecinos difieren solo en un número. Por ejemplo, 1111 y 1110 son vecinos, porque solo tiene que cambiar un dígito para convertir el primero en el segundo).
Huang demostró que esta esquina debe tener al menos tantos vecinos como la raíz cuadrada del número de dígitos, en este caso, la raíz cuadrada de 4, que es 2.
Para dimensiones bajas, puede decir que esto es cierto simplemente marcando. No es tan difícil verificar 16 coordenadas en el cubo (o "cadenas") para vecinos, por ejemplo. Pero cada vez que agrega una dimensión al cubo, el número de cadenas se duplica. Entonces el problema se vuelve más difícil de verificar muy rápidamente
El conjunto de cadenas de 30 dígitos de largo, las coordenadas de las esquinas de un cubo de 30 dimensiones, tiene más de mil millones de cadenas diferentes, lo que significa que el cubo tiene más de mil millones de esquinas. Con cadenas de 200 dígitos, hay más de un novemdecillón. Eso es un millón de billones de billones de billones de billones de billones de billones, o 1 seguido de 60 ceros.
Es por eso que a los matemáticos les gustan las pruebas: muestran que algo es cierto en todos los casos, no solo los fáciles.
"Si norte es igual a un millón, esto significa que tenemos cadenas de longitud de 1 millón, entonces la conjetura es que si tomas 2 ^ 1,000,000-1 y sumas 1, entonces hay una cadena que tiene 1,000 vecinos, la raíz cuadrada de un millón, "Dijo Kalai.
El último avance importante en la conjetura de la sensibilidad se produjo en 1988, dijo Kalai, cuando los investigadores probaron que una cadena debe tener al menos el logaritmo de norte vecinos. Ese es un número mucho menor; el logaritmo de 1,000,000 es solo 6. Entonces la prueba de Huang descubrió que al menos otros 994 vecinos están ahí afuera.
Una prueba elegante y "misteriosa"
"Es muy misterioso", dijo Kalai sobre la prueba de Huang. "Utiliza 'métodos espectrales', que son métodos muy importantes en muchas áreas de las matemáticas. Pero usa métodos espectrales de una manera novedosa. Todavía es misterioso, pero creo que podemos esperar que esta nueva forma de usar métodos espectrales tenga gradualmente más aplicaciones."
En esencia, Huang conceptualizó el hipercubo utilizando matrices de números en filas y columnas (llamadas matrices). Huang descubrió una forma completamente inesperada de manipular una matriz con una disposición inusual de -1s y 1s que "mágicamente hace que todo funcione", escribió Aaronson en su blog.
Huang "tomó esta matriz y la modificó de una manera muy ingeniosa y misteriosa", dijo Kalai. "Es como si tuvieras una orquesta y tocan algo de música, y luego dejas que algunos de los jugadores, no sé, se pongan de cabeza, y la música se vuelve completamente diferente, algo así".
Esa música diferente resultó ser la clave para probar la conjetura, dijo Kalai. Es misterioso, dijo, porque aunque los matemáticos entienden por qué el método funcionó en este caso, no entienden completamente esta nueva "música" o en qué otros casos podría ser útil o interesante.
"Durante 30 años, no hubo progreso, y luego Hao Huang resolvió este problema, y encontró una prueba muy simple de que la respuesta es la raíz cuadrada de norte", Dijo Kalai." Pero durante estos 30 años ... la gente se dio cuenta de que esta pregunta es muy importante en la teoría de la informática ".
La prueba de Huang es emocionante porque avanza el campo de la informática, dijo Kalai. Pero también es notable porque introdujo un método novedoso, y los matemáticos aún no están seguros de qué otra cosa podría permitirles lograr con el nuevo método de Huang.
