Le mathématicien Emory Hao Huang dit que l'outil algébrique qu'il a développé pour résoudre le problème "pourrait également avoir un certain potentiel pour être appliqué à d'autres problèmes combinatoires et de complexité importants pour l'informatique". Crédit :Université Emory
La conjecture de sensibilité est l'une des plus importantes, et déroutant, problèmes ouverts en informatique théorique pendant près de trois décennies. Il semble avoir finalement rencontré son match grâce au travail de Hao Huang, professeur adjoint de mathématiques à l'Université Emory.
Huang présentera une preuve de la conjecture de sensibilité lors de la Conférence internationale sur les structures et algorithmes aléatoires, fixé pour Zurich, La Suisse, 15 au 19 juillet.
"Je m'attaque à ce problème par intermittence depuis 2012, " Huang dit, « mais l'idée clé m'est apparue il y a à peine une semaine. J'ai finalement identifié le bon outil pour la résoudre. »
Huang a publié la preuve sur sa page d'accueil et cela a rapidement généré un buzz parmi les mathématiciens et les informaticiens sur les réseaux sociaux, qui ont loué sa concision et sa simplicité remarquables.
La conjecture de sensibilité concerne les données booléennes, qui mappe les informations en un vrai-faux, ou 1-0 binaire. Les fonctions booléennes jouent un rôle important dans la théorie de la complexité, ainsi que dans la conception de circuits et de puces pour ordinateurs numériques.
"En mathématiques, une fonction booléenne est l'un des sujets discrets les plus élémentaires, tout comme les nombres, des graphiques ou des formes géométriques, ", explique Huang.
Il existe de nombreuses mesures de complexité d'une fonction booléenne, et presque tous, y compris la complexité de l'arbre de décision, la complexité du certificat, la complexité des requêtes aléatoires et bien d'autres sont connues pour être polynomiales. Cependant, il y a un cas inconnu, la soi-disant sensibilité d'une fonction booléenne, qui mesure la sensibilité de la fonction lors du changement d'une entrée à la fois.
En 1994, les mathématiciens Noam Nisan et Mario Szegedy ont proposé la conjecture de sensibilité concernant ce cas inconnu.
"Leur conjecture dit que la sensibilité d'une fonction booléenne est également polynomiale liée aux autres mesures, " dit Huang. " Si c'est vrai, alors il cesserait d'être une valeur aberrante et il rejoindrait le reste d'entre eux."
Huang a développé une méthode algébrique pour prouver la conjecture. "J'espère que cette méthode pourrait également avoir un certain potentiel pour être appliquée à d'autres problèmes combinatoires et de complexité importants pour l'informatique, " il dit.
