La conjetura de la sensibilidad se ha mantenido como una de las más importantes, y desconcertante, problemas abiertos en la informática teórica durante casi tres décadas. Parece que finalmente encontró su pareja a través del trabajo de Hao Huang. profesor asistente de matemáticas en la Universidad de Emory.

Huang presentará una prueba de la Conjetura de Sensibilidad durante la Conferencia Internacional sobre Estructuras y Algoritmos Aleatorios, listo para Zurich, Suiza, 15 al 19 de julio.

"He estado atacando este problema de forma intermitente desde 2012, "Huang dice, "pero la idea clave surgió para mí hace aproximadamente una semana. Finalmente identifiqué la herramienta adecuada para resolverlo".

Huang publicó la prueba en su página de inicio y pronto generó entusiasmo entre matemáticos e informáticos en las redes sociales. que han elogiado su notable concisión y sencillez.

La conjetura de sensibilidad se relaciona con datos booleanos, que mapea la información en un verdadero-falso, o binario 1-0. Las funciones booleanas juegan un papel importante en la teoría de la complejidad, así como en el diseño de circuitos y chips para computadoras digitales.

"En matemáticas, una función booleana es uno de los temas discretos más básicos, al igual que los números, gráficos o formas geométricas, "Huang explica.

Hay muchas medidas de complejidad de una función booleana, y casi todos, incluida la complejidad del árbol de decisiones, la complejidad del certificado, la complejidad de las consultas aleatorias y muchas otras, se sabe que están relacionadas polinomialmente. Sin embargo, hay un caso desconocido, la llamada sensibilidad de una función booleana, que mide la sensibilidad de la función al cambiar una entrada a la vez.

En 1994, Los matemáticos Noam Nisan y Mario Szegedy propusieron la Conjetura de Sensibilidad sobre este caso desconocido.

"Su conjetura dice que la sensibilidad de una función booleana también está relacionada polinomialmente con las otras medidas, "Dice Huang." Si es verdad, entonces dejaría de ser un caso atípico y se uniría al resto de ellos ".

Huang desarrolló un método algebraico para probar la conjetura. "Espero que este método también tenga algún potencial para aplicarse a otros problemas combinatorios y de complejidad importantes para la informática, " él dice.