Un matematico ha risolto un problema di 30 anni al confine tra matematica e informatica. Ha usato una prova innovativa ed elegante che i suoi colleghi si meravigliano della sua semplicità.
Hao Huang, un assistente professore di matematica alla Emory University di Atlanta, ha dimostrato un'idea matematica chiamata congettura di sensibilità, che, in termini incredibilmente approssimativi, sostiene quanto puoi cambiare l'input in una funzione senza cambiare l'output (questo è la sua sensibilità).
Nei decenni trascorsi da quando i matematici hanno proposto per la prima volta la congettura della sensibilità (senza dimostrarla), gli informatici teorici hanno capito che ha enormi implicazioni per determinare i modi più efficienti per elaborare le informazioni.
La cosa straordinaria della dimostrazione di Huang, secondo altri esperti del settore, non è solo il fatto che Huang ce l'ha fatta, ma anche il modo elegante e diretto in cui l'ha fatta. La sua prova non è stata ufficialmente rivista o pubblicata su alcun giornale di matematica. Ma subito dopo che Huang lo ha messo online il 1 ° luglio, i suoi colleghi lo hanno rapidamente accettato come un fatto.
"Ogni volta che c'è un annuncio come questo", ha scritto sul suo blog lo scienziato informatico teorico dell'Università di Texas Scott Aaronson, "~ il 99% delle volte o la prova è sbagliata, o comunque è troppo complicata per gli estranei per valutarla rapidamente. Questo è uno dei restanti 1% dei casi. Sono piuttosto fiducioso che la prova sia corretta. Perché? Perché l'ho letta e compresa. Mi ci è voluto circa mezz'ora. "
Ryan O'Donnell, un professore di informatica che studia teoria dei numeri alla Carnegie Mellon University di Pittsburgh, ha sottolineato che la prova di Huang può essere riassunta in un singolo tweet:
Cosa ha effettivamente dimostrato Huang?
Per semplicità, immagina un cubo 3D con lati lunghi 1 unità ciascuno. Se si inserisce questo cubo in un sistema di coordinate 3D (nel senso che ha misure in tre direzioni), un angolo avrebbe le coordinate (0,0,0), quello accanto a esso potrebbe essere (1,0,0), il uno sopra potrebbe essere (0,1,0) e così via. Puoi prendere metà degli angoli (quattro angoli) senza avere una coppia di vicini: (0,0,0), (1,1,0), (1,0,1) e (0,1,1) non sono ' vicini di casa. Puoi mostrarlo guardando il cubo, ma lo sappiamo anche perché tutti sono diversi per più di una coordinata.
La congettura della sensibilità riguarda la ricerca di quanti vicini hai quando prendi più della metà degli angoli di un cubo di dimensione superiore, o di un ipercubo, ha detto il matematico dell'Università ebraica Gil Kalai. Puoi scrivere le coordinate dell'ipercubo come stringhe di 1 e 0, dove il numero di dimensioni è la lunghezza della stringa, ha detto Kalai a Live Science. Per un ipercubo 4D, ad esempio, ci sono 16 punti diversi, il che significa 16 stringhe diverse di 1 e 0 che sono lunghe quattro cifre.
Ora scegli metà più 1 singolo punto sull'ipercubo (per un ipercubo 4D, ciò significa scegliere nove - o 8 + 1 - punti diversi su un totale di 16).
Da questo set più piccolo, trova il punto con il maggior numero di vicini: qual è il minimo numero di vicini che può avere? (I vicini differiscono di un solo numero. Ad esempio, 1111 e 1110 sono vicini, poiché è necessario scambiare solo una cifra per trasformare la prima nella seconda.)
Huang ha dimostrato che questo angolo deve avere almeno tanti vicini quanti la radice quadrata del numero di cifre - in questo caso, la radice quadrata di 4 - che è 2.
Per dimensioni ridotte, puoi dire che è vero solo controllando. Ad esempio, non è difficile controllare 16 coordinate sul cubo (o "stringhe") per i vicini. Ma ogni volta che aggiungi una dimensione al cubo, il numero di stringhe raddoppia. Quindi il problema diventa più difficile da controllare molto rapidamente.
L'insieme di stringhe lunghe 30 cifre - le coordinate agli angoli di un cubo tridimensionale - contiene oltre 1 miliardo di stringhe diverse, il che significa che il cubo ha più di 1 miliardo di angoli. Con stringhe lunghe 200 cifre, ce ne sono più di un novembre. Sono un milione di miliardi di miliardi di miliardi di miliardi, ovvero 1 seguito da 60 zero.
Ecco perché ai matematici piacciono le prove: dimostrano che qualcosa è vero in ogni caso, non solo quelli facili.
"Se n è uguale a un milione - questo significa che abbiamo stringhe di lunghezza 1 milione - quindi la congettura è che se prendi 2 ^ 1.000.000-1 e aggiungi 1, allora c'è una stringa che ha 1.000 vicini - la radice quadrata di un milione, "Disse Kalai.
L'ultimo grande progresso nella congettura della sensibilità è arrivato nel 1988, ha detto Kalai, quando i ricercatori hanno dimostrato che una stringa deve avere almeno il logaritmo di n vicinato. Questo è un numero molto più basso; il logaritmo di 1.000.000 è solo 6. Quindi la prova di Huang ha appena scoperto che almeno 994 altri vicini sono là fuori.
Una prova elegante e "misteriosa"
"È molto misterioso", ha detto Kalai delle prove di Huang. "Utilizza" metodi spettrali ", che sono metodi molto importanti in molte aree della matematica. Ma utilizza metodi spettrali in un modo nuovo. È ancora misterioso, ma penso che possiamo aspettarci che questo nuovo modo di usare i metodi spettrali avrà gradualmente più applicazioni ".
In sostanza, Huang ha concettualizzato l'ipercubo usando matrici di numeri in righe e colonne (chiamate matrici). Huang ha scoperto un modo completamente inaspettato di manipolare una matrice con una disposizione insolita di -1 e 1 che "magicamente fa funzionare tutto", ha scritto Aaronson sul suo blog.
Huang "ha preso questa matrice e l'ha modificata in un modo molto ingegnoso e misterioso", ha detto Kalai. "È come se tu avessi un'orchestra e loro suonassero un po 'di musica, e poi lasci che alcuni dei musicisti, non lo so, stiano in testa e la musica diventa completamente diversa - qualcosa del genere."
Quella musica diversa si è rivelata la chiave per provare la congettura, ha detto Kalai. È misterioso, ha detto, perché anche se i matematici comprendono perché il metodo ha funzionato in questo caso, non comprendono appieno questa nuova "musica" o in quali altri casi potrebbe essere utile o interessante.
"Per 30 anni non ci sono stati progressi, quindi Hao Huang ha risolto questo problema e ha trovato una prova molto semplice che la risposta è la radice quadrata di n", Ha detto Kalai" Ma durante questi 30 anni ... la gente ha capito che questa domanda è molto importante nella teoria dell'informatica ".
La prova di Huang è eccitante perché fa avanzare il campo dell'informatica, ha detto Kalai. Ma è anche degno di nota perché ha introdotto un nuovo metodo e i matematici non sono ancora sicuri di cos'altro il nuovo metodo di Huang potrebbe consentire loro di realizzare.
