Hao Huang demuestra después de 30 años la llamada conjetura de la sensibilidad, que se engloba en la teoría de la complejidad computacional
9 de agosto de 2019 – Agencias.
Cuando un problema matemático importante, que lleva 30 años propuesto, acaba por resolverse en dos escasas páginas de razonamiento, no cabe más que darse la enhorabuena. Como aquel sacrificio de dama en una partida de ajedrez que fascina por la creatividad de su estratega, esas dos páginas de inventiva matemática son un regalo para cualquier admirador de la disciplina. Su autor, Hao Huang, matemático e informático teórico de la Universidad de Emory (EE UU), probó la llamada conjetura de la sensibilidad en un artículo de seis páginas (dos de demostración y el resto para centrar el contexto y para enunciar consecuencias y derivadas del resultado), que publicó a principios de julio en ArXiV, un repositorio abierto de artículos científicos. Unas horas después las redes sociales ya se felicitaban. El influyente blog de Gil Kalai, de la Universidad Hebrea de Jerusalén, anunciaba: “Increíble: ¡Hao Huang demuestra la conjetura de la sensibilidad!”. Al rato, Ryan O’Donnell, investigador de Carnegie Mellon, comprimía las dos milagrosas páginas en los 282 caracteres de un tuit.
Cuando un problema matemático importante, que lleva 30 años propuesto, acaba por resolverse en dos escasas páginas de razonamiento, no cabe más que darse la enhorabuena. Como aquel sacrificio de dama en una partida de ajedrez que fascina por la creatividad de su estratega, esas dos páginas de inventiva matemática son un regalo para cualquier admirador de la disciplina. Su autor, Hao Huang, matemático e informático teórico de la Universidad de Emory (EE UU), probó la llamada conjetura de la sensibilidad en un artículo de seis páginas (dos de demostración y el resto para centrar el contexto y para enunciar consecuencias y derivadas del resultado), que publicó a principios de julio en ArXiV, un repositorio abierto de artículos científicos. Unas horas después las redes sociales ya se felicitaban. El influyente blog de Gil Kalai, de la Universidad Hebrea de Jerusalén, anunciaba: “Increíble: ¡Hao Huang demuestra la conjetura de la sensibilidad!”. Al rato, Ryan O’Donnell, investigador de Carnegie Mellon, comprimía las dos milagrosas páginas en los 282 caracteres de un tuit.
La conjetura de la sensibilidad fue enunciada por Noam Nisan y Mario Szegedy en 1989, y se engloba en la informática teórica, en concreto la teoría de la complejidad computacional, con aplicaciones a la teoría de la elección social. Tomar decisiones no es tarea fácil. Para hacerlo, tanto máquinas como humanos nos apoyamos en reglas de decisión o algoritmos, es decir, métodos sistemáticos previamente diseñados. Supongamos que debemos tomar una decisión binaria, sí o no, basados en el resultado de un número (N) de datos, también binarios. Por ejemplo, podría tratarse de aprobar o no un texto legal, basándonos en los votos de un cuerpo electoral (cada voto sería uno de los datos).
Algunas de estas reglas de decisión serán más sensibles a los cambios en los datos que otras. En el ejemplo anterior, si la elección se basa en la opinión mayoritaria de la totalidad de los electores, entonces el resultado es sensible a exactamente la mitad más una de las opiniones: si exactamente N/2+1 de los votantes aprobaron el texto, un cambio de opinión de cualquiera de esos electores haría cambiar el resultado. De forma general, se dice que una regla de decisión es sensible para ciertos datos, si cambiando uno de ellos se cambia la decisión final. El grado de sensibilidad de la regla de decisión es el máximo número de datos a los que la regla puede ser sensible en el peor de los casos (es decir, en los casos frontera extremos).
Siguiendo con el ejemplo anterior, si dividimos a los electores en K distritos electorales iguales y basamos el resultado de la elección en que al menos uno de los distritos apruebe el texto por consenso, entonces la sensibilidad de la regla de decisión se reduce a N/K, o a K, según cuál sea mayor. Efectivamente, los casos frontera extremos se dan cuando exactamente un distrito alcanza el consenso, o cuando todos se quedan a un voto del consenso. En el primer caso solo N/K cambios de opinión podrían afectar al resultado, mientras que en el segundo solo K.
Así es como el grado de sensibilidad de una regla de decisión se puede tomar como baremo para determinar su adecuación en ciertos procesos electorales. Sin embargo, mientras que en algunos contextos está bien motivado y es fácil de determinar, en otros casos no. Por ejemplo, para valorar si una regla de decisión es adecuada para activar o no un nivel de emergencia, pongamos, de riesgo de incendio de una máquina. Para ello, se emplean como datos las mediciones de ciertos parámetros. Se empieza por la temperatura ambiente; si esta excede un cierto nivel, se mide el nivel de humedad; en caso contrario, se mide el nivel de agua del radiador. Cuantas menos mediciones se requieran, mejor. En este caso, valoramos la adecuación de la regla de decisión en base a la complejidad de preguntas, y este es otro de los muchos baremos para reglas de decisión.
Pero ¿se puede establecer alguna relación entre estos baremos? Sabemos que la complejidad de preguntas de una regla de decisión no puede ser menor que su grado de sensibilidad, puesto que si alguna de las mediciones sensibles queda sin respuesta, la decisión no puede estar determinada. ¿Podría ser que, a su vez, hubiera una relación inversa? Precisamente eso postula la conjetura de la sensibilidad: que, sea cual sea la regla de decisión, su complejidad de preguntas es menor que una potencia de su grado de sensibilidad. Combinada con la observación anterior, la conjetura, ahora teorema gracias a Huang, establece que el grado de sensibilidad y la complejidad de preguntas son, a escala logarítmica, baremos equivalentes.
En sus escasas dos páginas de argumentación, Huang demuestra la conjetura apoyándose en resultados previos que redujeron el problema a uno sobre subgrafos inducidos del hipercubo N-dimensional. Huang, que es un especialista de la teoría espectral de grafos, redujo a su vez el problema a uno sobre valores propios de matrices de signos. El célebre Teorema de Entrelazados de Cauchy hizo el resto.
Se da la circunstancia que Huang estaba en Madrid cuando dio con la solución (su mujer estaba visitando el ICMAT). Según cuenta, se refugiaba en la habitación de su hotel durante la espectacular ola de calor que asedió Europa a finales de junio. Al parecer el calor duró lo justo y necesario para que Huang pudiese completar, en aquellos pocos días, 30 años de búsqueda.
