La congettura della sensibilità è stata una delle più importanti, e sconcertante, problemi aperti nell'informatica teorica da quasi tre decenni. Sembra aver finalmente trovato la sua corrispondenza grazie al lavoro di Hao Huang, un assistente professore di matematica alla Emory University.

Huang presenterà una prova della congettura di sensibilità durante la Conferenza internazionale su strutture e algoritmi casuali, fissato per Zurigo, Svizzera, dal 15 al 19 luglio

"Ho attaccato questo problema a intervalli dal 2012, "Huang dice, "ma l'idea chiave è emersa per me circa una settimana fa. Ho finalmente individuato lo strumento giusto per risolverla."

Huang ha pubblicato la dimostrazione sulla sua home page e presto ha suscitato scalpore tra matematici e informatici sui social media, che ne hanno elogiato la notevole concisione e semplicità.

La congettura di sensibilità si riferisce a dati booleani, che mappa le informazioni in un vero-falso, o binario 1-0. Le funzioni booleane giocano un ruolo importante nella teoria della complessità, nonché nella progettazione di circuiti e chip per computer digitali.

"In matematica, una funzione booleana è uno degli argomenti discreti più elementari, proprio come i numeri, grafici o forme geometriche, "Spiega Huang.

Ci sono molte misure di complessità di una funzione booleana, e quasi tutti, compresa la complessità dell'albero decisionale, la complessità del certificato, la complessità della query randomizzata e molte altre sono note per essere correlate in modo polinomiale. Però, c'è un caso sconosciuto, la cosiddetta sensibilità di una funzione booleana, che misura la sensibilità della funzione quando si modifica un ingresso alla volta.

Nel 1994, i matematici Noam Nisan e Mario Szegedy hanno proposto la Congettura di sensibilità riguardo a questo caso sconosciuto.

"La loro congettura dice che la sensibilità di una funzione booleana è anche correlata polinomialmente alle altre misure, " dice Huang. "Se è vero, allora cesserebbe di essere un valore anomalo e si unirebbe al resto di loro".

Huang ha sviluppato un metodo algebrico per dimostrare la congettura. "Spero che questo metodo possa anche avere del potenziale per essere applicato ad altri problemi combinatori e di complessità importanti per l'informatica, " lui dice.