Matematičar je riješio problem star 30 godina na granici između matematike i informatike. Koristio je inovativan, elegantan dokaz koji svoje kolege zadivljuje svojom jednostavnošću.
Hao Huang, docent matematike na sveučilištu Emory u Atlanti, dokazao je matematičku ideju nazvanu pretpostavkom osjetljivosti, koja, na nevjerojatno grub način, iznosi tvrdnju o tome koliko možete promijeniti ulaz u funkciju bez promjene rezultata (ovo je njegova osjetljivost).
U desetljećima otkad su matematičari prvi put predložili pretpostavku osjetljivosti (ne dokazujejući je), teorijski računalni znanstvenici shvatili su da ima ogromne implikacije za utvrđivanje najučinkovitijih načina obrade informacija.
Prema drugim stručnim stručnjacima, Huangin dokaz nije samo to što ga je Huang skinuo, već i elegantan i neposredan način na koji je to učinio. Njegov dokaz nije službeno recenziran niti objavljen u nijednom matematičkom časopisu. Ali ubrzo nakon što ga je Huang stavio na mrežu 1. srpnja, kolege su ga brzo prihvatile kao činjenicu.
"Kad god postoji ovakva najava", napisao je na svom blogu sveučilište Teksasa u Austinu teorijski informatičar Scott Aaronson, "u 99% slučajeva ili je dokaz pogrešan, ili je u svakom slučaju previše komplicirano da ga procijene. brzo. Ovo je jedan od preostalih 1% slučajeva. Prilično sam uvjeren da je dokaz tačan. Zašto? Zato što sam ga pročitao i razumio. Trebalo mi je oko pola sata. "
Ryan O'Donnell, profesor informatike koji proučava teoriju brojeva na Sveučilištu Carnegie Mellon u Pittsburghu, istaknuo je da se Huangov dokaz može sažeti u jednom tvitu:
Što je zapravo dokazao Huang?
Radi jednostavnosti, zamislite 3D kocku sa stranicama duljine 1 jedinica. Ako ovu kocku stavite u 3D koordinatni sustav (što znači da ima mjerenja u tri smjera), jedan ugao bi imao koordinate (0,0,0), a jedan pored njega (1,0,0), jedan iznad može biti (0,1,0) i tako dalje. Možete uzeti polovinu uglova (četiri ugla), a da nemate komšija: (0,0,0), (1,1,0), (1,0,1) i (0,1,1) aren ' t susjedi. To možete pokazati gledajući kocku, ali mi to također znamo jer su sve različite po više koordinata.
Pretpostavka o osjetljivosti odnosi se na pronalaženje koliko susjeda imate kada uzmete više od pola uglova kocke veće dimenzije ili hiperkube, rekao je matematičar sa Sveučilišta Hebrew Gil Kalai. Koordinate hiperkube možete napisati kao nizove 1 i 0, gdje je broj dimenzija duljina niza, rekao je Kalai za Live Science. Primjerice, za 4D hiperkubu postoji 16 različitih točaka, što znači 16 različitih niza od 1 i 0 koji su četiri znamenke.
Sada odaberite pola plus 1 pojedinačne točke na hiperkubi (za 4D hiperkubu to znači da biste odabrali devet - ili 8 + 1 - različite točke od ukupno 16).
Iz ovog manjeg seta pronađite poantu s najviše susjeda - što je minimum koliko komšija može imati? (Susjedi se razlikuju za samo jedan broj. Na primjer, 1111 i 1110 su susjedi, jer morate zamijeniti samo jednu znamenku da biste prvu pretvorili u drugu.)
Huang je dokazao da ovaj ugao mora imati najmanje onoliko susjeda koliko je kvadratni korijen broja znamenki - u ovom slučaju četvrtasti korijen 4 - što je 2.
Ako se radi o malim dimenzijama, to možete reći samo provjerom. Na primjer, nije teško provjeriti 16 koordinata na kocki (ili "žice") za susjede. Ali svaki put kada kocki dodate dimenziju, broj žice se udvostručuje. Dakle, problem postaje teže provjeriti vrlo brzo.
Skup stringova koji je dugačak 30 znamenki - koordinate do uglova 30-dimenzionalne kocke - ima više od milijardu različitih žica u sebi, što znači da kocka ima više od milijardu uglova. S nizovima duljinama od 200 znamenki, postoji više od novemdecliiona. To je milijun milijardi milijardi milijardi milijardi, ili 1, a slijedi 60 nula.
To je razlog zašto matematičari vole dokaze: Oni pokazuju da je u svakom slučaju nešto istinsko, a ne samo lako.
"Ako n jednak je milionu - to znači da imamo nizove duljine 1 milijun - onda je pretpostavka da ako uzmete 2 ^ 1.000.000-1 i dodate 1, postoji niz koji ima 1.000 susjeda - kvadratni korijen od milijun, "Rekao je Kalai.
Posljednji veliki napredak u pretpostavci osjetljivosti dogodio se 1988. godine, rekao je Kalai, kad su istraživači dokazali da jedan niz mora imati barem logaritam n Komšije. To je mnogo manji broj; logaritam od 1.000.000 je samo 6. Dakle, Huangin je dokaz upravo otkrio da je najmanje 994 drugih susjeda vani.
Elegantan i "tajanstven" dokaz
"Vrlo je tajanstveno", rekao je Kalai zbog Huanginog dokaza. "Koristi" spektralne metode ", koje su vrlo važne metode u mnogim područjima matematike. No, spektralne metode koristi na nov način. Još uvijek je tajanstveno, ali mislim da možemo očekivati da će se ovaj novi način korištenja spektralnih metoda postepeno pojaviti više aplikacija. "
U osnovi, Huang je konceptualizirao hiperkubu pomoću nizova brojeva u redovima i stupovima (zvanih matrice). Huang je smislio potpuno neočekivan način manipuliranja matricom s neobičnim rasporedom -1 i 1 koji "magično čini da sve to djeluje", napisao je Aaronson na svom blogu.
Huang je "uzeo ovu matricu i modificirao je na vrlo genijalan i tajanstven način", rekao je Kalai. "To je kao da imate orkestar i oni puštaju neku glazbu, a zatim pustite da neki od svirača, ne znam, stoji na njihovoj glavi i glazba postane potpuno drugačija - nešto takvo."
Ta drugačija glazba pokazala se ključnom za dokazivanje nagađanja, rekao je Kalai. To je tajanstveno, rekao je, jer iako matematičari razumiju zašto je metoda funkcionirala u ovom slučaju, oni ne razumiju u potpunosti ovu novu "glazbu" niti u kojim bi drugim slučajevima ona mogla biti korisna ili zanimljiva.
"30 godina nije bilo napretka. Hao Huang je riješio ovaj problem i pronašao je vrlo jednostavan dokaz da je odgovor kvadratni korijen n", Rekao je Kalai." Ali tijekom tih 30 godina ... ljudi su shvatili da je ovo pitanje vrlo važno u teoriji računanja. "
Huang je dokaz uzbudljiv jer napreduje u području informatike, rekao je Kalai. Ali to je i značajno jer je uvela novu metodu, a matematičari još uvijek nisu sigurni što bi im nova Huangova nova metoda mogla omogućiti.
