Emory-matematikern Hao Huang säger att det algebraiska verktyget som han utvecklade för att ta itu med problemet "kan också ha en viss potential att tillämpas på andra kombinatoriska och komplexitetsproblem som är viktiga för datavetenskap." Kredit:Emory University
Känslighetsförmodan har stått som en av de viktigaste, och förbryllande, öppna problem inom teoretisk datavetenskap i nästan tre decennier. Det verkar äntligen ha mött sin match genom arbete av Hao Huang, en biträdande professor i matematik vid Emory University.
Huang kommer att presentera ett bevis på känslighetsförmodan under den internationella konferensen om slumpmässiga strukturer och algoritmer, inställd på Zürich, Schweiz, 15 till 19 juli.
"Jag har attackerat det här problemet av och på sedan 2012, "Huang säger, "men nyckelidén dök upp för mig för ungefär en vecka sedan. Jag hittade äntligen rätt verktyg för att lösa det."
Huang lade upp beviset på sin hemsida och det skapade snart surr bland matematiker och datavetare på sociala medier, som har prisat dess anmärkningsvärda koncishet och enkelhet.
Känslighetsförmodan relaterar till booleska data, som mappar information till en sann-falsk, eller 1-0 binärt. Booleska funktioner spelar en viktig roll i komplexitetsteorin, samt vid design av kretsar och chips för digitala datorer.
"I matematik, en boolesk funktion är ett av de mest grundläggande diskreta ämnena – precis som siffror, grafer eller geometriska former, " förklarar Huang.
Det finns många komplexitetsmått för en boolesk funktion, och nästan alla – inklusive beslutsträdets komplexitet, certifikatets komplexitet, den randomiserade frågekomplexiteten och många andra – är kända för att vara polynomrelaterade. Dock, det finns ett okänt fall, den så kallade känsligheten för en boolesk funktion, som mäter hur känslig funktionen är när man ändrar en ingång i taget.
År 1994, matematikerna Noam Nisan och Mario Szegedy föreslog känslighetsförmodan om detta okända fall.
"Deras gissningar säger att känsligheten för en boolesk funktion också är polynomiellt relaterad till de andra måtten, " säger Huang. "Om det är sant, då skulle det upphöra att vara en outlier och det skulle förena sig med resten av dem."
Huang utvecklade en algebraisk metod för att bevisa gissningen. "Jag hoppas att den här metoden också kan ha en viss potential att tillämpas på andra kombinatoriska och komplexitetsproblem som är viktiga för datavetenskap, " han säger.
