Matematik vyriešil 30-ročný problém na hranici matematiky a informatiky. Využil inovatívny a elegantný dôkaz, ktorý jeho kolegov obdivuje jeho jednoduchosť.
Hao Huang, odborný asistent matematiky na Emory University v Atlante, preukázal matematický nápad nazývaný citlivosť dohad, ktorý v neuveriteľne drsnom vyjadrení tvrdí, o koľko môžete zmeniť vstup na funkciu bez toho, aby ste zmenili výstup (toto je jeho citlivosť).
V priebehu desaťročí, keď matematici prvýkrát navrhli domnienku citlivosti (bez toho, aby ju dokázali), si teoretickí počítačoví vedci uvedomili, že má obrovské dôsledky na určenie najúčinnejších spôsobov spracovania informácií.
Čo je pozoruhodné na dôkazoch spoločnosti Huang, podľa iných odborníkov v tejto oblasti nie je to len to, že to spoločnosť Huang stiahla, ale aj elegantný a priamy spôsob, akým to urobil. Jeho dôkaz nebol oficiálne recenzovaný alebo publikovaný v žiadnom matematickom časopise. Ale čoskoro potom, čo ho spoločnosť Huang uviedla online 1. júla, jeho kolegovia to rýchlo prijali.
„Kedykoľvek dôjde k takémuto oznámeniu,“ napísala na svojom blogu teoretická počítačová vedkyňa z University of Texas Scott Aaronson, „~ 99% času je dôkaz nesprávny alebo v každom prípade je pre cudzincov príliš zložitý na jeho vyhodnotenie. rýchlo. Toto je jeden zo zostávajúcich 1% prípadov. Som si celkom istá, že dôkaz je správny. Prečo? Pretože som ho čítal a rozumel mu. Trvalo mi to asi pol hodiny. “
Ryan O'Donnell, profesor informatiky, ktorý študuje teóriu čísel na Univerzite Carnegie Mellon University v Pittsburghu, zdôraznil, že Huangov dôkaz možno zhrnúť do jediného tweetu:
Čo Huang skutočne preukázal?
Pre jednoduchosť si predstavte 3D kocku so stranami, z ktorých každá je 1 jednotka. Ak umiestnite túto kocku do 3D súradnicového systému (čo znamená, že má merania v troch smeroch), jeden roh by mal mať súradnice (0,0,0), ten vedľa neho by mohol byť (1,0,0), jedna nad ňou by mohla byť (0,1,0) a tak ďalej. Môžete mať polovicu rohov (štyri rohy) bez toho, aby ste mali susedov: (0,0,0), (1,1,0), (1,0,1) a (0,1,1) arén ' t susedia. Môžete to ukázať pri pohľade na kocku, ale tiež to vieme, pretože všetky z nich sa líšia o viac ako jednu súradnicu.
Citlivosť dohad je o zistení, koľko susedov máte, keď budete mať viac ako polovicu rohov vyššej dimenzionálnej kocky alebo hyperkocky, povedal matematik Hebrejskej univerzity Gil Kalai. Súradnice hyperkocky môžete napísať ako reťazce 1 s a 0 s, kde počet rozmerov je dĺžka reťazca, povedal Kalai Live Science. Napríklad pre 4D hyperkocku je 16 rôznych bodov, čo znamená 16 rôznych reťazcov 1 s a 0 s, ktoré sú štyri číslice dlhé.
Teraz vyberte polovicu plus 1 jednotlivé body na hypercube (pre 4D hypercube, to znamená vybrať deväť - alebo 8 + 1 - rôzne body z celkového počtu 16).
Z tohto menšieho súboru nájdite bod s najväčšími susedmi - čo je minimum počet susedov, ktoré môže mať? (Susedia sa líšia iba jedným číslom. Napríklad 1111 a 1110 sú susedia, pretože na zmenu prvej na druhú stačí vymeniť iba jednu číslicu.)
Huang preukázal, že tento roh musí mať najmenej toľko susedov, ako druhá odmocnina počtu číslic - v tomto prípade druhá odmocnina 4 - čo je 2.
Pri nízkych rozmeroch môžete povedať, že je to pravda len kontrolou. Nie je také ťažké napríklad skontrolovať 16 súradníc na kocke (alebo „reťazcoch“) susedov. Ale vždy, keď do kocky pridáte rozmer, počet reťazcov sa zdvojnásobí. Takže problém sa dá skontrolovať veľmi rýchlo.
Sada reťazcov dlhých 30 číslic - súradnice rohov 30-rozmernej kocky - obsahuje viac ako 1 miliardu rôznych reťazcov, čo znamená, že kocka má viac ako 1 miliardu rohov. S reťazcami dlhými 200 číslic je viac ako novemdecillion. To je milión miliárd miliárd miliárd miliárd miliárd miliárd, alebo 1 nasledovaný 60 nulami.
To je dôvod, prečo matematici radi dokazujú: Ukazujú, že v každom prípade platí niečo, nielen jednoduché.
"Ak n rovná sa miliónu - to znamená, že máme reťazce s dĺžkou 1 milión - potom sa predpokladá, že ak vezmete 2 ^ 1 000 000-1 a pridáte 1, potom existuje reťazec, ktorý má 1 000 susedov - druhá odmocnina milióna, „Povedal Kalai.
Posledný významný pokrok v dohľade o citlivosti prišiel v roku 1988, uviedol Kalai, keď vedci dokázali, že jeden reťazec musí mať aspoň logaritmus n susedia. To je oveľa nižšie číslo; logaritmus 1 000 000 je iba 6. Takže Huangov dôkaz práve zistil, že je tam najmenej 994 ďalších susedov.
Elegantný a „záhadný“ dôkaz
„Je to veľmi tajomné,“ povedal Kalai o dôkaze Huang. „Používa„ spektrálne metódy “, ktoré sú veľmi dôležitými metódami v mnohých oblastiach matematiky. Ale používa spektrálne metódy novým spôsobom. Je to stále záhadné, myslím si však, že môžeme očakávať, že tento nový spôsob využívania spektrálnych metód bude mať postupne viac aplikácií. “
Huang v podstate konceptualizoval hypercube pomocou polí čísel v riadkoch a stĺpcoch (nazývaných matice). Huang prišiel na úplne neočakávaný spôsob manipulácie s maticou s neobvyklým usporiadaním -1 s a 1s, ktoré „magicky robí všetko funkčným,“ napísal Aaronson na svoj blog.
Huang „vzal túto maticu a upravil ju veľmi dômyselne a záhadne,“ povedal Kalai. „Je to, akoby ste mali orchester a hrajú nejakú hudbu, a potom necháte niektorých hráčov, neviem, stáť na hlave a hudba sa stáva úplne inou - niečo také.“
Táto odlišná hudba sa ukázala byť kľúčom k preukázaniu domnienky, uviedol Kalai. Je to záhadné, povedal, pretože hoci matematici chápu, prečo metóda v tomto prípade fungovala, úplne nerozumejú tejto novej „hudbe“ alebo v iných prípadoch by to mohlo byť užitočné alebo zaujímavé.
„Za 30 rokov nedošlo k žiadnemu pokroku a potom Hao Huang vyriešil tento problém a našiel veľmi jednoduchý dôkaz, že odpoveď je druhá odmocnina n„Ale počas týchto 30 rokov si ľudia uvedomili, že táto otázka je v teórii výpočtovej techniky veľmi dôležitá.“
Huangov dôkaz je vzrušujúci, pretože napreduje v oblasti počítačovej vedy, uviedol Kalai. Je to však pozoruhodné aj preto, že zaviedla novú metódu a matematici si stále nie sú istí, čo im ešte Huangova nová metóda umožňuje.
