Un matematician a rezolvat o problemă de 30 de ani la granița dintre matematică și informatică. A folosit o dovadă inovatoare, elegantă, care îi face pe colegii săi să se minuneze de simplitatea sa.
Hao Huang, profesor asistent de matematică la Universitatea Emory din Atlanta, a dovedit o idee matematică numită conjectură de sensibilitate, care, în termeni incredibil de grosolan, face o afirmație despre cât poți schimba intrarea într-o funcție fără a schimba ieșirea (aceasta este sensibilitatea sa).
În deceniile de când matematicienii au propus pentru prima dată conjectura de sensibilitate (fără a o dovedi), informaticienii teoreticieni și-au dat seama că are implicații uriașe pentru determinarea celor mai eficiente modalități de procesare a informațiilor.
Ceea ce este remarcabil în legătură cu dovada lui Huang, potrivit altor experți în domeniu, nu este doar faptul că Huang a scos-o, ci și modul elegant și simplu în care a făcut-o. Dovada lui nu a fost oficial revizuită de la egal la egal sau publicată în niciun jurnal de matematică. Dar la scurt timp după ce Huang a pus-o online 1 iulie, colegii săi au acceptat-o repede ca faptă.
„Ori de câte ori există un anunț de genul acesta”, a scris pe blogul său Universitatea din Texas, la informaticianul teoretician din Austin, Scott Aaronson, „~ 99% din timp, fie dovada este greșită, fie în orice caz este prea complicat pentru străini să o evalueze. Acesta este unul dintre restul de 1% din cazuri. Sunt mai degrabă încrezător că dovada este corectă. De ce? Pentru că am citit-o și am înțeles-o. Mi-a luat cam o jumătate de oră. "
Ryan O'Donnell, profesor de informatică care studiază teoria numerelor la Universitatea Carnegie Mellon din Pittsburgh, a subliniat că dovada lui Huang poate fi rezumată într-un singur tweet:
Ce a dovedit de fapt Huang?
Pentru simplitate, imaginați-vă un cub 3D cu laturi care au fiecare o unitate lungă. Dacă introduceți acest cub într-un sistem de coordonate 3D (ceea ce înseamnă că are măsurători în trei direcții), un colț ar avea coordonatele (0,0,0), cel de lângă acesta ar putea fi (1,0,0), unul deasupra ar putea fi (0,1,0) și așa mai departe. Puteți lua jumătate din colțuri (patru colțuri) fără să aveți vreo pereche de vecini: (0,0,0), (1,1,0), (1,0,1) și (0,1,1) nu sunt ” vecini. Puteți arăta acest lucru uitându-vă la cub, dar îl știm și pentru că toți sunt diferiți de mai multe coordonate.
Conjectura de sensibilitate este despre a găsi câți vecini aveți atunci când luați mai mult de jumătate din colțurile unui cub dimensional superior sau al unui hipercub, a spus Gil Kalai, matematicianul universității ebraice. Puteți scrie coordonatele hipercubului sub formă de șiruri de 1s și 0s, unde numărul de dimensiuni este lungimea șirului, a spus Kalai pentru Live Science. Pentru un hipercub 4D, de exemplu, există 16 puncte diferite, ceea ce înseamnă 16 șiruri diferite de 1s și 0s care au patru cifre.
Acum alege jumătate plus 1 puncte individuale pe hipercub (pentru un hipercub 4D, adică alege nouă - sau 8 + 1 - puncte diferite dintr-un total de 16).
Din acest set mai mic, găsiți punctul cu cei mai mulți vecini - care este minim numărul de vecini pe care îi poate avea? (Vecinii diferă cu un singur număr. De exemplu, 1111 și 1110 sunt vecini, deoarece trebuie doar să schimbați o cifră pentru a transforma prima în a doua.)
Huang a dovedit că acest colț trebuie să aibă cel puțin la fel de mulți vecini ca rădăcina pătrată a numărului de cifre - în acest caz, rădăcina pătrată a 4 - care este 2.
Pentru dimensiuni reduse, puteți spune că acest lucru este adevărat doar verificând. Nu este chiar atât de greu să verifici 16 coordonate pe cub (sau „șiruri”) pentru vecini, de exemplu. Dar de fiecare dată când adăugați o dimensiune la cub, numărul de șiruri se dublează. Deci problema devine mai greu de verificat foarte repede.
Setul de șiruri cu o lungime de 30 de cifre - coordonatele la colțurile unui cub cu 30 de dimensiuni - are peste 1 miliard de șiruri diferite în el, ceea ce înseamnă că cubul are mai mult de 1 miliard de colțuri. Cu șiruri care au o lungime de 200 de cifre, există mai mult de o nouă miliardă. Acesta este un milion de miliarde de miliarde de miliarde de miliarde de miliarde de euro, sau 1 urmată de 60 de zero.
Acesta este motivul pentru care matematicienilor le plac dovezile: arată că ceva este adevărat în fiecare caz, nu doar în cele ușoare.
"Dacă n este egal cu un milion - asta înseamnă că avem șiruri cu lungimea de 1 milion - atunci conjectura este că dacă luați 2 ^ 1.000.000-1 și adăugați 1, atunci există un șir care are 1.000 de vecini - rădăcina pătrată a unui milion, "A spus Kalai.
Ultimul avans major în conjectura de sensibilitate a venit în 1988, a spus Kalai, când cercetătorii au dovedit că un șir trebuie să aibă cel puțin logaritmul n vecini. Acesta este un număr mult mai mic; logaritmul de 1.000.000 este de doar 6. Deci, dovada lui Huang tocmai a descoperit că cel puțin 994 alți vecini sunt acolo.
O dovadă elegantă și „misterioasă”
„Este foarte misterios”, a spus Kalai despre dovada lui Huang. "Utilizează" metode spectrale ", care sunt metode foarte importante în multe domenii ale matematicii. Dar folosește metode spectrale într-un mod inedit. Este încă misterios, dar cred că ne putem aștepta ca acest mod inedit de a utiliza metodele spectrale va avea treptat mai multe aplicații. "
În esență, Huang a conceptualizat hipercubul folosind tablouri de numere în rânduri și coloane (numite matrici). Huang și-a dat seama de un mod complet neașteptat de a manipula o matrice cu un aranjament neobișnuit de -1s și 1s, care „face ca totul să funcționeze”, a scris Aaronson pe blogul său.
Huang „a luat această matrice și a modificat-o într-un mod foarte ingenios și misterios”, a spus Kalai. "Este ca și cum ai avea o orchestră și ar cânta ceva muzică, iar apoi îi lași pe unii dintre jucători, nu știu, să stea pe capul lor, iar muzica devine complet diferită - ceva de genul acesta."
Că muzica diferită s-a dovedit a fi cheia pentru dovedirea conjecturii, a spus Kalai. A spus că este misterios, pentru că, deși matematicienii înțeleg de ce metoda a funcționat în acest caz, nu înțeleg pe deplin această nouă „muzică” sau în ce alte cazuri ar putea fi utilă sau interesantă.
"Timp de 30 de ani, nu s-au înregistrat progrese și atunci Hao Huang a soluționat această problemă și a găsit o dovadă foarte simplă că răspunsul este rădăcina pătrată a n", A spus Kalai. Dar în acești 30 de ani ... oamenii și-au dat seama că această întrebare este foarte importantă în teoria informaticii."
Dovada lui Huang este interesantă deoarece avansează domeniul informaticii, a spus Kalai. Dar este de remarcat, de asemenea, pentru că a introdus o metodă nouă, iar matematicienii încă nu sunt siguri ce altceva noua metodă a lui Huang le-ar putea permite să realizeze.
