Calor y sensibilidad

Hao Huang en uno de sus viajes

Hao Huang, un joven y brillante matemático chino de Shantou, graduado en la Universidad de Pekín, doctorado en UCLA y actualmente profesor de la Universidad de Emory (Estados Unidos), ha demostrado la llamada Conjetura de la Sensibilidad, cuya demostración se resistía a matemáticos y teóricos de la informática desde 1989, hace ya 30 años.

¿Qué en qué consiste el que desde ahora es ya el Teorema de la Sensibilidad? Pues tiene que ver con los algoritmos (métodos matemáticos o simplificando, fórmulas) complejos para tomar una decisión final que puede ser un sí o un no. Hay varios métodos formales de describir numéricamente un algoritmo de decisión. En concreto, se puede cuantificar su grado de complejidad, que depende del número de mediciones o variables individuales que intervengan en el algoritmo de decisión. 

Por ejemplo, para decidir si el riesgo de incendio es preocupante existe el famoso algoritmo de los tres treintas, según el cual más de 30º de temperatura, más de 30 km/h de velocidad del aire y menos del 30 % de humedad relativa suponen un riesgo de incendio muy alto. En ese caso el algoritmo depende de tres mediciones o variables, su grado de complejidad es 3.

Por otro lado, también se puede cuantificar su sensibilidad, o dependencia del resultado final frente a pequeñas variaciones en los datos individuales que intervienen. Por ejemplo, si en algún momento hay una votación que se decide por mayoría simple, un solo voto puede decidir e inclinar la balanza hacia uno u otro lado. El grado de sensibilidad de un algoritmo de decisión es el número máximo de datos individuales a los que el algoritmo puede llegar a ser sensible si se dan las circunstancias adecuadas.

Lógicamente, el grado de sensibilidad siempre será menor que el grado de complejidad. Pues bien, el Teorema de la Sensibilidad describe en detalle la relación entre esos dos grados y establece que el grado de complejidad es proporcional al grado de sensibilidad elevado a cuatro.

Hay varias circunstancias que han rodeado a la demostración que son realmente llamativas. En primer lugar, Hao Huang ha necesitado solo dos páginas para demostrar la conjetura (véase su artículo) y otro matemático, Ryan O'Donnell (Universidad Carnegie Mellon), ha resumido la demostración en los 282 caracteres de un tuit:

 

Ex.1: ∃edge-signing of n-cube with 2^{n-1} eigs each of +/-sqrt(n) 

Interlacing=>Any induced subgraph with >2^{n-1} vtcs has max eig >= sqrt(n) 

Ex.2: In subgraph, max eig <= max valency, even with signs 

Hence [GL92] the Sensitivity Conj, s(f) >= sqrt(deg(f))

Y por otro lado, parece que nuestro matemático se encontraba en Madrid cuando tuvo su Eureka particular, encerrado en la habitación de hotel porque no aguantaba la ola de calor de finales de junio pasado, mientras su mujer, también matemática, visitaba el Instituto de Ciencias Matemáticas (ICMAT) de la Universidad Autónoma de Madrid. Y es que a veces, no hay bien que por calor no venga.

No me resisto a resumirlo en forma de cuento:

Érase una vez un joven y brillante matemático chino, que viajó de vacaciones a Madrid junto a su esposa un caluroso verano, para conocer la capital española. Pero una ola de calor, extraordinariamente intensa, hizo que decidiera quedarse un día entero en el hotel, cerca del aire acondicionado y sin pisar la calle, mientras su mujer recorría la ciudad.

Como se aburría, se puso a repasar fórmulas y teoremas en los márgenes de los folletos turísticos que tenía a mano y hete aquí que encontró una maravillosa demostración, tan elegante que cabe en un tuit, del teorema que contiene la fórmula que relaciona la sensibilidad con la complejidad. Y es que cuanto más complejo es un sistema, más sensible es, también al calor. 

Publicado por Antonio F. Rodríguez.