Egy matematikus egy 30 éves problémát oldott meg a matematika és a számítástechnika közötti határon. Olyan innovatív, elegáns bizonyítékot használt, amely kollégái csodálkoztak az egyszerűségén.
Hao Huang, az atlantai Emory Egyetem matematikai asszisztensének bizonyított egy érzékenységi feltevésnek nevezett matematikai ötlet, amely hihetetlenül durván kifejezve azt állítja, hogy mennyire változtathatja meg a funkció bemenetét a kimenet megváltoztatása nélkül (ez az érzékenysége).
Azon évtizedek óta, amikor a matematikusok először javasolták az érzékenységi sejtést (anélkül, hogy ezt bizonyították volna), az elméleti számítógépes tudósok rájöttek, hogy ennek hatalmas következményei vannak az információfeldolgozás leghatékonyabb módjainak meghatározására.
Ami a másik szakértő szerint figyelemre méltó Huang bizonyítékában, nem csak az, hogy Huang lerázta, hanem az elegáns és egyértelmű módon is, amellyel megtette. Bizonyítását hivatalosan nem recenzálták és nem tették közzé egyetlen matematikai folyóiratban sem. De hamarosan, miután Huang július 1-jén internetet tett, kollégái gyorsan elfogadták azt tényként.
"Ha bármilyen ilyen hirdetmény van" - írta Scott Aaronson az austini texasi egyetem elméleti számítógépes tudósa -, az idő ~ 99% -a vagy a bizonyíték hibás, vagy mindenesetre túlságosan bonyolult a kívülállók számára annak értékeléséhez. gyorsan. Ez az esetek egyike a fennmaradó 1% -nak. Nagyon magabiztos vagyok abban, hogy a bizonyítás megfelelő. Miért? Mert olvastam és megértettem. Kb. fél óra. "
Ryan O'Donnell, a számításelméletet a pittsburghi Carnegie Mellon Egyetemen tanulmányozó számítástechnikai professzor rámutatott, hogy Huang bizonyítékait egyetlen tweettel lehet összefoglalni:
Mit bizonyított Huang?
Az egyszerűség kedvéért képzelj el egy 3D-s kocka oldalt, amelyek mindegyike egy egység hosszú. Ha ezt a kocka 3D-s koordinátarendszerbe helyezi (azaz három irányban van mérve), akkor az egyik sarok koordinátái (0,0,0), a mellette lévő pedig (1,0,0) lesz, az egyik fölött lehet (0,1,0) és így tovább. A sarkok felét (négy sarkot) úgy veheti igénybe, hogy nincs pár szomszédja: (0,0,0), (1,1,0), (1,0,1) és (0,1,1) aren '. t szomszédok. Ezt megmutathatja a kocka nézésével, de azt is tudjuk, mert mindegyik több mint egy koordináta különbözik egymástól.
Az érzékenység feltételezése az, hogy megtudja, hány szomszédja van, ha magasabb dimenziós kocka vagy hiperkocka több mint felét veszi el - mondta Gil Kalai, a Héber Egyetem matematikusa. A hiperkocka koordinátáit 1-es és 0-os karakterláncok formájában írhatja, ahol a méretek száma megegyezik a karakterlánc hosszával - mondta Kalai a Live Science-nek. Például egy 4D hiperkocka számára 16 különböző pont van, ami 16 különféle 1 és 0 karakterláncot jelent, amelyek négy számjegyűek.
Most válassza ki a plusz 1 plusz pontot a hiperkockán (egy 4D-es hibakocka esetében ez azt jelenti, hogy kilenc - vagy 8 + 1 - különböző pontot válasszon a 16-ból).
Ebből a kisebb készletből keresse meg a pontot a legtöbb szomszéddal - mi az minimális szomszédok száma lehet? (A szomszédok csak egy számmal különböznek egymástól. Például az 1111 és az 1110 szomszédok, mert csak egy számjegyet kell cserélni, hogy az elsőt a másodikvá változtassuk.)
Huang bebizonyította, hogy ebben a sarokban legalább annyi szomszédnak kell lennie, mint a számjegyek négyzetgyöke - ebben az esetben a négyzetgyöke 4 -, amely 2.
Alacsony méretek esetén elmondhatja, hogy ez igaz, csak ellenőrizve. Nem olyan nehéz ellenőrizni például a kocka 16 koordinátáját (vagy "karakterláncokat") a szomszédok esetében. De minden alkalommal, amikor hozzáad egy dimenziót a kockahoz, a húrok száma megduplázódik. Tehát a problémát egyre nehezebb ellenőrizni.
A 30 számjegyből álló húrkészlet - a 30-dimenziós kocka sarkainak koordinátái - több mint egymilliárd különféle húrokkal rendelkezik, azaz a kocka több, mint 1 milliárd sarka van. 200 számjegyű húrokkal több, mint egy novemdeillió létezik. Ez egy milliárd milliárd milliárd milliárd milliárd, vagyis 1, amelyet 60 nulla követ.
Ezért szeretik a matematikusok a bizonyítékokat: Megmutatják, hogy valami mindenben igaz, nem csak az egyszerű.
"Ha n egyenlő egy millióval - ez azt jelenti, hogy 1 millió hosszú húrokkal rendelkezzünk - akkor az a feltételezés, hogy ha 2 ^ 1 000 000-1-et veszünk és hozzáadunk 1-t, akkor van egy string, amelyben 1000 szomszéd van - egy millió négyzetgyöke, "Mondta Kalai.
Kalai szerint az érzékenységi feltevés utolsó jelentős előrelépése 1988-ban történt, amikor a kutatók bebizonyították, hogy az egyik húrnak legalább a következőnek kell lennie: n szomszédok. Ez sokkal alacsonyabb szám; az 1.000.000 logaritmus mindössze 6. Tehát Huang bizonyítéka csak rájött, hogy legalább 994 másik szomszéd van odakint.
Elegáns és "titokzatos" bizonyíték
"Nagyon titokzatos" - mondta Kalai Huang bizonyítékáról. "A" spektrális módszereket "használja, amelyek nagyon fontos módszerek a matematika sok területén. De a spektrális módszereket újszerűen alkalmazza. Még mindig rejtélyes, de szerintem azt várhatjuk, hogy a spektrális módszerek újszerű módon fokozatosan további alkalmazások. "
Lényegében Huang fogalmazta meg a hiperkocka sorokban és oszlopokban lévő számmátrixok felhasználásával (mátrixoknak nevezett). Huang kitalált egy teljesen váratlan módszert egy mátrix manipulálására szokatlan -1s és 1s elrendezéssel, amely "varázslatosan mindent megtesz" - írta Aaronson a blogjában.
Huang "átvette ezt a mátrixot, és nagyon ötletesen és rejtélyes módon módosította" - mondta Kalai. "Olyan, mintha van egy zenekar, és zenét játszanak, aztán hagyod, hogy néhány játékos, nem tudom, álljon a fejükön, és a zene teljesen másképp válik - valami ilyesmire."
Kalai szerint ez a különféle zene bizonyult a kulcsszónak a sejtés bizonyításában. Rejtélyes - mondta, mert bár a matematikusok megértik, hogy miért működött a módszer ebben az esetben, nem értik meg teljesen ezt az új „zenét”, vagy más esetekben hasznos vagy érdekes lehet.
"30 évig nem volt előrelépés, majd Hao Huang rendezte ezt a problémát, és nagyon egyszerű bizonyítékot talált arra, hogy a válasz négyzetgyöke n"- mondta Kalai. - De a 30 év alatt ... az emberek rájöttek, hogy ez a kérdés nagyon fontos a számítástechnika elméletében."
Huang bizonyítéka izgalmas, mert tovább halad a számítástechnika területén - mondta Kalai. Figyelemre méltó még azért is, mert új módszert vezet be, és a matematikusok még mindig nem biztosak abban, hogy Huang új módszere mégis mit tehet lehetővé nekik.
