Het gevoeligheidsvermoeden is een van de belangrijkste, en verbijsterend, bijna drie decennia lang openstaande problemen in de theoretische informatica. Het lijkt eindelijk zijn gelijke te hebben gevonden door het werk van Hao Huang, een assistent-professor wiskunde aan de Emory University.

Huang zal een bewijs van het gevoeligheidsvermoeden presenteren tijdens de internationale conferentie over willekeurige structuren en algoritmen, op weg naar Zürich, Zwitserland, 15 tot 19 juli.

"Ik val dit probleem sinds 2012 af en toe aan, "Huang zegt, "maar ongeveer een week geleden kwam het belangrijkste idee voor mij naar voren. Ik heb eindelijk de juiste tool gevonden om het op te lossen."

Huang plaatste het bewijs op zijn homepage en het veroorzaakte al snel een buzz onder wiskundigen en computerwetenschappers op sociale media. die zijn opmerkelijke beknoptheid en eenvoud hebben geprezen.

Het gevoeligheidsvermoeden heeft betrekking op booleaanse gegevens, die informatie in een true-false, of 1-0 binair. Booleaanse functies spelen een belangrijke rol in de complexiteitstheorie, evenals in het ontwerp van circuits en chips voor digitale computers.

"In wiskunde, een booleaanse functie is een van de meest elementaire discrete onderwerpen - net als getallen, grafieken of geometrische vormen, " legt Huang uit.

Er zijn veel complexiteitsmaten van een booleaanse functie, en bijna allemaal - inclusief de complexiteit van de beslissingsboom, de complexiteit van het certificaat, de gerandomiseerde query-complexiteit en vele andere - staan ​​​​bekend als polynoom gerelateerd. Echter, er is één onbekend geval, de zogenaamde gevoeligheid van een booleaanse functie, die meet hoe gevoelig de functie is bij het wijzigen van één ingang tegelijk.

1994, wiskundigen Noam Nisan en Mario Szegedy stelden het Gevoeligheidsvermoeden voor met betrekking tot dit onbekende geval.

"Hun vermoeden zegt dat de gevoeligheid van een booleaanse functie ook polynoom gerelateerd is aan de andere maatregelen, " zegt Huang. "Als het waar is, dan zou het ophouden een uitbijter te zijn en zou het zich bij de rest voegen."

Huang ontwikkelde een algebraïsche methode om het vermoeden te bewijzen. "Ik hoop dat deze methode ook enig potentieel heeft om te worden toegepast op andere combinatorische en complexiteitsproblemen die belangrijk zijn voor de informatica, " hij zegt.