La conjetura de "sensibilidad" dejó perplejos a
muchos de los mejores científicos informáticos, pero la nueva prueba es tan
simple que un investigador lo resumió en un solo tweet.
Dave Whyte para la revista Quanta
Un artículo
publicado en línea este mes ha resuelto una
conjetura de casi 30 años sobre la estructura de los componentes fundamentales
de los circuitos de computadoras. Esta conjetura de
"sensibilidad" ha dejado perplejos a muchos de los científicos
informáticos más destacados a lo largo de los años, pero la nueva prueba es tan
simple que un investigador lo resumió en un solo tweet.
“Esta conjetura se
ha mantenido como uno de los problemas abiertos más frustrantes y vergonzosos
de toda la combinatoria y la informática teórica", escribió Scott Aaronson, de la
Universidad de Texas, Austin, en una publicación de blog . "La lista de personas que intentaron
resolverlo y fracasó es como un quién es quién de matemáticas discretas y
ciencias de la computación teórica", agregó en un correo electrónico.
La conjetura se refiere a funciones booleanas,
reglas para transformar una cadena de bits de entrada (0s y 1s) en un solo bit
de salida. Una de estas reglas es generar un 1 siempre que cualquiera de
los bits de entrada sea 1, y un 0 de lo contrario; otra regla es generar
un 0 si la cadena tiene un número par de 1, y un 1 en caso contrario. Cada
circuito de computadora es una combinación de funciones booleanas, lo que los
convierte en "los ladrillos y el mortero de lo que sea que estés haciendo
en informática", dijo Rocco
Servedio, de la Universidad de Columbia."Me resulta difícil imaginar que incluso Dios sabe cómo probar
la Conjetura de Sensibilidad de una manera más sencilla que esta"
A lo largo de los años, los científicos
informáticos han desarrollado muchas formas de medir la complejidad de una
función booleana dada. Cada medida captura un aspecto diferente de cómo la
información en la cadena de entrada determina el bit de salida. Por ejemplo,
la "sensibilidad" de una función booleana rastrea, en términos
generales, la probabilidad de que al voltear un solo bit de entrada alterará el
bit de salida. Y la "complejidad de la consulta" calcula la
cantidad de bits de entrada que debe consultar antes de que pueda estar seguro
de la salida.
Cada medida proporciona una ventana única en la
estructura de la función booleana. Sin embargo, los científicos
informáticos han descubierto que casi todas estas medidas encajan en un marco
unificado, por lo que el valor de cualquiera de ellas es un indicador
aproximado del valor de las demás. Solo una medida de complejidad no
parecía encajar: la sensibilidad.
En 1992, Noam Nisan de la Universidad Hebrea de Jerusalén y Mario
Szegedy , ahora de la Universidad de
Rutgers, conjeturaron que la sensibilidad realmente encaja en este
marco. Pero nadie pudo probarlo. "Esto,
yo diría, probablemente fue la pregunta abierta pendiente en el estudio de las
funciones booleanas", dijo Servedio.
"La gente
escribió artículos largos y complicados tratando de lograr el más mínimo
progreso", dijo Ryan O'Donnell, de la Universidad Carnegie Mellon.
Ahora Hao Huang, un matemático de la Universidad de Emory, ha
demostrado la conjetura de sensibilidad con un ingenioso pero elemental
argumento de dos páginas sobre la combinatoria de puntos en cubos. "Es simplemente hermoso, como una perla
preciosa", escribió Claire
Mathieu , del Centro Nacional Francés
para la Investigación Científica, durante una entrevista en Skype.
Aaronson y O'Donnell llamaron al documento de Huang
la prueba del "libro" de la conjetura de sensibilidad, refiriéndose
a la
noción de Paul
Erd de un libro celestial en el que
Dios escribe la prueba perfecta de todo teorema. "Me resulta difícil imaginar que incluso Dios sabe cómo probar la
conjetura de sensibilidad de una manera más simple que esto", escribió Aaronson .
Una materia sensible
“Imagínese”, dijo Mathieu, que está completando una serie de
preguntas de sí / no en una solicitud de préstamo bancario. “Cuando haya terminado, el banquero anotará
sus resultados y le dirá si califica para un préstamo. Este proceso es una
función booleana: sus respuestas son los bits de entrada y la decisión del
banco es el bit de salida”.
Si se rechaza su solicitud, puede preguntarse si
podría haber cambiado el resultado mintiendo sobre una sola pregunta; tal vez,
al afirmar que gana más de $ 50,000 cuando realmente no lo hace. Si esa
mentira hubiera cambiado el resultado, los científicos informáticos dicen que
la función booleana es "sensible" al valor de ese bit en particular. Si,
por ejemplo, hay siete mentiras diferentes que podría haber dicho que habrían
arrojado por separado el resultado, entonces para su perfil de préstamo, la
sensibilidad de la función booleana es de siete.
Los
científicos informáticos definen la sensibilidad general de la función booleana
como el mayor valor de sensibilidad cuando se analizan todos los diferentes
perfiles de préstamo posibles. En cierto sentido, esta medida calcula
cuántas de las preguntas son realmente importantes en la mayoría de los casos
límite, las aplicaciones que podrían haberse desplazado más fácilmente de la
otra forma si hubieran sido tan diferentes.
Lucy
Reading-Ikkanda / Quanta Magazine
La sensibilidad suele ser una de las medidas de
complejidad más fáciles de calcular, pero está lejos de ser la única medida iluminadora. Por
ejemplo, en lugar de entregarle una solicitud en papel, el banquero podría
haberle entrevistado, comenzando con una sola pregunta y luego utilizando su
respuesta para determinar qué pregunta formular a continuación. El mayor
número de preguntas que el banquero tendría que hacer antes de tomar una
decisión es la complejidad de la consulta de la función booleana.
Esta medida surge en una gran cantidad de
configuraciones; por ejemplo, un médico puede querer enviar a un paciente para
la menor cantidad de pruebas posible antes de llegar a un diagnóstico, o un
experto en aprendizaje automático puede desear que un algoritmo examine el
menor número posible de características de un objeto. antes de
clasificarlo "En muchas situaciones, situaciones de diagnóstico o
situaciones de aprendizaje, está realmente contento si la regla subyacente ...
tiene una baja complejidad de consulta", dijo O'Donnell.
Otras medidas consisten en buscar la forma más
sencilla de escribir la función booleana como una expresión matemática, o
calcular cuántas respuestas tendría que mostrar el jefe a un jefe para
demostrar que habían tomado la decisión de préstamo correcta. Incluso hay
una versión de física cuántica de complejidad de consulta en la que el banquero
puede hacer una "superposición" de varias preguntas al mismo
tiempo. Descubrir cómo se relaciona esta medida con otras medidas de
complejidad ha ayudado a los investigadores a comprender las limitaciones
de los algoritmos cuánticos.
Con la única excepción de la sensibilidad, los
científicos informáticos demostraron que todas estas medidas están
estrechamente relacionadas. Específicamente, tienen una relación polinomial
entre sí; por ejemplo, una medida podría ser aproximadamente el cuadrado o el
cubo o la raíz cuadrada de otra. Sólo la sensibilidad se negó
obstinadamente a encajar en esta clara caracterización.
Muchos investigadores sospecharon que sí pertenecía, pero no pudieron probar que no existían funciones booleanas extrañas cuya sensibilidad tuviera una relación exponencial más que polinómica con las otras medidas, lo que en este contexto significaría que la medida de sensibilidad es muy amplia. Más pequeño que las otras medidas."Esta pregunta fue una espina en los lados de la gente durante 30 años", dijo Aaronson.
Muchos investigadores sospecharon que sí pertenecía, pero no pudieron probar que no existían funciones booleanas extrañas cuya sensibilidad tuviera una relación exponencial más que polinómica con las otras medidas, lo que en este contexto significaría que la medida de sensibilidad es muy amplia. Más pequeño que las otras medidas."Esta pregunta fue una espina en los lados de la gente durante 30 años", dijo Aaronson.
Arrinconar la solución
Huang escuchó sobre la conjetura de sensibilidad a
fines de 2012, durante el almuerzo con el matemático Michael
Saks en el Instituto de Estudios
Avanzados, donde Huang era un becario postdoctoral. Fue tomado
inmediatamente con la simplicidad y elegancia de la conjetura. "A
partir de ese momento, me obsesioné mucho con pensar en ello", dijo.
Huang agregó la conjetura de sensibilidad a una "lista secreta" de problemas
en los que estaba interesado, y cada vez que aprendía sobre una nueva
herramienta matemática, consideraba si podía ayudar. "Cada vez que publicaba un nuevo artículo, siempre volvía a este
problema", dijo. "Por
supuesto, me rendiría después de cierto tiempo y trabajaré en un problema más
realista".
El matemático Hao Huang durante unas vacaciones recientes en
Lisboa.
Huang sabía, al igual que la comunidad de investigación más
amplia, que la conjetura de sensibilidad podría resolverse si los matemáticos
pudieran demostrar una conjetura fácil de establecer sobre colecciones de
puntos en cubos de diferentes dimensiones. Hay una forma natural de pasar
de una cadena de n 0s
y 1s a un punto en un cubo n- dimensional:
simplemente use los n bits
como las coordenadas del punto.
Por ejemplo, las cuatro cadenas de dos bits (00,
01, 10 y 11) corresponden a las cuatro esquinas de un cuadrado en el plano
bidimensional: (0,0), (0,1), (1,0) y (1,1). Del mismo modo, las ocho
cadenas de tres bits corresponden a las ocho esquinas de un cubo
tridimensional, y así sucesivamente en las dimensiones más altas. Una
función booleana, a su vez, puede considerarse como una regla para colorear
estas esquinas con dos colores diferentes (por ejemplo, rojo para 0 y azul para
1).
En 1992, Craig Gotsman , ahora del Instituto de Tecnología de Nueva
Jersey, y Nati Linial, de la
Universidad Hebrea, descubrieron que probar la conjetura de sensibilidad puede
reducirse a responder una pregunta simple sobre cubos de diferentes
dimensiones: si elige cualquier colección de más de La mitad de las esquinas de
un cubo y colorealas de rojo, ¿siempre hay algún punto rojo que está conectado
a muchos otros puntos rojos? (Aquí, por "conectado", queremos decir que los dos puntos comparten
uno de los bordes externos del cubo, en lugar de estar en una diagonal)."Espero que este otoño se enseñe, en una sola conferencia, en
todos los cursos de combinatoria del nivel de maestría".
Si su colección contiene exactamente la mitad de
las esquinas del cubo, es posible que ninguna de ellas esté conectada. Por
ejemplo, entre las ocho esquinas del cubo tridimensional, los cuatro puntos
(0,0,0), (1,1,0), (1,0,1) y (0,1,1) están todos sentados a través de diagonales
entre sí. Pero tan pronto como más de la mitad de los puntos en un cubo de
cualquier dimensión se colorean en rojo, deben aparecer algunas conexiones
entre los puntos rojos. La pregunta es: ¿Cómo se distribuyen estas
conexiones? ¿Habrá al menos un punto altamente conectado?
En 2013, Huang comenzó a pensar que la mejor manera
de entender esta pregunta podría ser a través del método estándar de
representar una red con una matriz que rastrea qué puntos están conectados y
luego examinar un conjunto de números llamados valores propios de la
matriz. Durante cinco años siguió revisando esta idea, sin
éxito. "Pero al menos pensar en eso [me ayudó] a dormirme rápidamente
muchas noches", comentó en la publicación del blog de Aaronson.
Luego, en 2018, a Huang se le ocurrió usar una
pieza de matemáticas de 200 años de antigüedad llamada teorema de entrelazado
de Cauchy, que relaciona los valores propios de una matriz con los de una
submatriz, lo que la convierte en la herramienta perfecta para estudiar la
relación entre un cubo y Un subconjunto de sus esquinas. Huang decidió
solicitar una subvención de la Fundación Nacional de Ciencia para explorar más
esta idea.
Luego, el mes pasado, mientras estaba sentado en un
hotel de Madrid escribiendo su propuesta de subvención, se dio cuenta
repentinamente de que podía llevar a este enfoque hasta su realización
simplemente cambiando los signos de algunos de los números en su
matriz. De esta manera, pudo probar que en cualquier colección de más de
la mitad de los puntos en un cubo n-dimensional, habrá algún
punto que esté conectado a al menos $ latex \ sqrt {n} $ de los otros puntos -
y la conjetura de sensibilidad siguió instantáneamente de este resultado. norte--√ de los otros puntos - y la conjetura de
sensibilidad se siguió instantáneamente de este resultado.
Cuando el papel de Huang aterrizó en la bandeja de entrada de
Mathieu, su primera reacción fue "uh-oh",
dijo. "Cuando un problema ha
estado alrededor de los 30 años y todo el mundo lo ha escuchado, es probable
que la prueba sea muy larga y tediosa y complicada, o que sea muy
profunda". Abrió el periódico esperando
no entender nada.
Pero la prueba era lo suficientemente simple para que Mathieu y
muchos otros investigadores pudieran digerir en una sola sesión. "Espero que este otoño se enseñe, en
una sola conferencia, en todos los cursos de combinatoria del nivel de
maestría", escribió a través de Skype.
El resultado de Huang es incluso más fuerte de lo
necesario para probar la conjetura de sensibilidad, y este poder debería
proporcionar nuevos conocimientos sobre las medidas de complejidad. "Se agrega a nuestro conjunto de
herramientas para tal vez tratar de responder otras preguntas en el análisis de
las funciones booleanas", dijo Servedio.
Sin embargo, lo más importante es que el resultado
de Huang descansa sobre las inquietantes preocupaciones sobre si la
sensibilidad podría ser algo extraño en el mundo de las medidas de complejidad,
dijo Servedio. "Creo que mucha
gente durmió más tranquila esa noche, después de enterarse de esto".
Fuente: Quanta
Magazine – Erica Klarreich Corresponsal Contribuyente
– 26 de julio de 2019
¿Qué es Quanta?
Albert
Einstein llamó a los fotones "quanta de luz".
El objetivo
de Quanta es "iluminar la ciencia"..
Sus reporteros
se centran en los desarrollos en matemáticas,
física teórica, informática teórica y ciencias
básicas de la vida.
Las
mejores organizaciones de noticias tradicionales brindan excelentes informes
sobre áreas de la ciencia aplicada, como la salud, la medicina, la tecnología,
la ingeniería y el medio ambiente.
En la revista Quanta,
la precisión científica es tan importante como contar una buena historia. Dado
que Quanta es una publicación sin
fines de lucro financiada por la Fundación Simons, todos sus recursos se
destinan a producir un periodismo responsable y de libre acceso que se
investiga, se publica, se edita, se copia y se verifica meticulosamente.
Fuente: Quanta Magazine
Traducción libre de Soca
No hay comentarios:
Publicar un comentario