Resuelto un famoso problema matem¨¢tico en dos p¨¢ginas condensadas en 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.

Albert Atserias es catedr¨¢tico de Inform¨¢tica Te¨®rica de la Universitat Polit¨¨cnica de Catalunya

Caf¨¦ y Teoremas es una secci¨®n dedicada a las matem¨¢ticas y al entorno en el que se crean, coordinada por el Instituto de Ciencias Matem¨¢ticas (ICMAT), en la que los investigadores y miembros del centro describen los ¨²ltimos avances de esta disciplina, comparten puntos de encuentro entre las matem¨¢ticas y otras expresiones sociales y culturales y recuerdan a quienes marcaron su desarrollo y supieron transformar caf¨¦ en teoremas. El nombre evoca la definici¨®n del matem¨¢tico h¨²ngaro Alfred R¨¦nyi: "Un matem¨¢tico es una m¨¢quina que transforma caf¨¦ en teoremas".

Edici¨®n y coordinaci¨®n: ?gata Tim¨®n (ICMAT).

Puedes seguir a Materia en Facebook, Twitter, Instagram o suscribirte aqu¨ª a nuestra newsletter