Matemaatik on lahendanud 30-aastase probleemi matemaatika ja arvutiteaduse piiril. Ta kasutas uuenduslikku ja elegantset tõestust, mille kolleegid imetlesid selle lihtsust.
Atlanta Emory ülikooli matemaatika abiprofessor Hao Huang tõestas matemaatilist ideed, mida nimetatakse tundlikkuse oletuseks, mis uskumatult jämedalt öeldes väidab, kui palju saate funktsiooni sisendit väljundit muutmata muuta (see on selle tundlikkus).
Aastakümnete jooksul pärast seda, kui matemaatikud esmalt pakkusid välja tundlikkuse oletuse (ilma seda tõestamata), taipasid teoreetilised arvutiteadlased, et sellel on teabe töötlemiseks kõige tõhusamate viiside kindlaksmääramisel tohutu mõju.
Mis on Huangi tõestuses tähelepanuväärne, pole selle valdkonna teiste ekspertide sõnul mitte ainult see, et Huang selle tõmbas, vaid ka elegantne ja sirgjooneline viis, kuidas ta seda tegi. Tema tõendit ei ole ametlikult eelretsenseeritud ega üheski matemaatikaajakirjas avaldatud. Kuid varsti pärast seda, kui Huang selle 1. juulil võrku pani, tunnistasid tema kolleegid seda kiiresti tõsiasjaks.
"Alati, kui on olemas selline teade," kirjutas Texase ülikooli Austini teoreetiline arvutiteadlane Scott Aaronson oma ajaveebis, "~ 99% ajast on kas tõend vale või igal juhul on see kõrvalistele isikutele liiga keeruline seda hinnata. kiiresti. See on üks järelejäänud 1% juhtudest. Olen üsna kindel, et tõendusmaterjal on õige. Miks? Sest lugesin ja sain sellest aru. Mul kulus umbes pool tundi. "
Pittsburghis Carnegie Melloni ülikoolis arvuteooriat õppiv arvutiteaduse professor Ryan O'Donnell tõi välja, et Huangi tõendi võib kokku võtta ühe säutsu abil:
Mida Huang tegelikult tõestas?
Kujutage lihtsuse huvides ette 3D-kuub, mille küljed on mõlemad 1 ühiku pikkused. Kui paned selle kuubi 3D-koordinaatsüsteemi (see tähendab, et sellel on mõõtmised kolmes suunas), oleks ühel nurgal koordinaadid (0,0,0), teisel võiks olla (1,0,0), üks selle kohal võib olla (0,1,0) ja nii edasi. Võite võtta pooled nurgad (neli nurka), ilma et oleks naabreid: (0,0,0), (1,1,0), (1,0,1) ja (0,1,1) pole ' t naabrid. Saate seda näidata kuupi vaadates, kuid me teame seda ka seetõttu, et nad kõik erinevad rohkem kui ühe koordinaadi võrra.
Heprea ülikooli matemaatik Gil Kalai ütles, et tundlikkuse oletus seisneb selles, kui palju naabreid on teil, kui võtate üle poole kõrgema mõõtmega kuubi või hüperkuubi nurkadest. Võite hüperkuubi koordinaadid kirjutada stringidena 1s ja 0, kus mõõtmete arv on stringi pikkus, rääkis Kalai Live Science'ile. Näiteks 4D hüperkuubi jaoks on 16 erinevat punkti, mis tähendab 16 erinevat numbrit 1-st ja 0-st, mis on neli numbrit pikad.
Nüüd vali hüperkuubil pool pluss 1 üksikpunkt (4D hüperkuubi puhul tähendab see, et vali üheksa - või 8 + 1 - punkt 16-st).
Sellest väiksemast komplektist leidke punkt kõige naabrite juures - mis see on miinimum kui palju naabreid sellel võib olla? (Naabrid erinevad vaid ühe numbri võrra. Näiteks 1111 ja 1110 on naabrid, sest esimese muutmiseks teiseks peate vahetama ainult ühe numbri.)
Huang tõestas, et selles nurgas peab olema vähemalt sama palju naabreid kui numbrite arvu ruutjuur - antud juhul ruutjuur 4 - mis on 2.
Madalate mõõtmete korral saate seda öelda lihtsalt kontrollides. Ei ole nii raske kontrollida näiteks naabrite kuubiku 16 koordinaati (või "stringe"). Kuid iga kord, kui lisate kuubikule mõõtme, kahekordistub stringide arv. Nii et seda probleemi on väga raske kontrollida.
30 numbri pikkuses stringide komplektis - 30-mõõtmelise kuubi nurkade koordinaadid - on selles üle miljardi erineva stringi, see tähendab, et kuubikul on rohkem kui 1 miljard nurka. 200 numbri pikkuste keelpillidega on rohkem kui novemdetsiljon. See on miljon miljardit miljardit miljardit miljardit ehk 1, millele järgneb 60 nulli.
Seetõttu meeldivad matemaatikutele tõendid: Need näitavad, et igal juhul on midagi tõsi, mitte ainult lihtsal.
"Kui n on võrdne miljoniga - see tähendab, et meil on stringe pikkusega 1 miljon -, siis eeldatakse, et kui võtta 2 ^ 1 000 000-1 ja lisada 1, siis on string, millel on 1000 naabrit - miljoni ruutjuur, "Ütles Kalai.
Viimane suurem edusamm tundlikkuse teeskluses jõudis Kalai sõnul 1988. aastal, kui teadlased tõestasid, et ühel stringil peab olema vähemalt logaritm n naabrid. See on palju väiksem arv; logaritm 1 000 000 on lihtsalt 6. Nii avastas Huangi tõend just, et seal on väljas vähemalt 994 muud naabrit.
Elegantne ja "salapärane" tõend
"See on väga salapärane," ütles Kalai Huangi tõest. "Ta kasutab" spektraalmeetodeid ", mis on väga olulised meetodid paljudes matemaatikavaldkondades. Kuid spektraalmeetodeid kasutatakse uudsel viisil. See on endiselt salapärane, kuid arvan, et võime eeldada, et see uudne spektraalmeetodite kasutamise viis on järk-järgult olemas. rohkem rakendusi. "
Sisuliselt käsitles Huang hüperkuubi, kasutades ridade ja veergude numbrimassiive (nn maatriksid). Huang mõtles välja täiesti ootamatu viisi maatriksiga manipuleerimiseks ebatavalise paigutusega -1s ja 1s, mis "võluväel paneb selle kõik toimima", kirjutas Aaronson oma blogis.
Huang "võttis selle maatriksi ja ta muutis seda väga leidlikult ja salapärasel viisil", ütles Kalai. "See on selline, nagu teil oleks orkester ja nad mängiksid muusikat, ja siis lasite mõnel mängijal, ma ei tea, neil peas seista ja muusika muutub hoopis teistsuguseks - millekski selliseks."
Kalai ütles, et see erinev muusika osutus võtmeks oletuse tõestamisel. Ta ütles, et see on salapärane, sest kuigi matemaatikud mõistavad, miks see meetod sel juhul töötas, ei mõista nad täielikult seda uut "muusikat" ega muudel juhtudel, kui see võib olla kasulik või huvitav.
"30 aasta jooksul ei olnud mingeid edusamme ja Hao Huang lahendas selle probleemi ning leidis väga lihtsa tõendi, et vastus on n"" Ütles Kalai. "Kuid nende 30 aasta jooksul said inimesed aru, et see küsimus on arvutusteoorias väga oluline."
Huangi tõendusmaterjal on põnev, kuna see edendab infotehnoloogia valdkonda, ütles Kalai. Kuid see on tähelepanuväärne ka seetõttu, et see tutvustas uudset meetodit ja matemaatikud pole endiselt kindlad, mida veel Huangi uus meetod võimaldab neil saavutada.
