Matematikas išsprendė 30 metų problemą ties riba tarp matematikos ir informatikos. Jis panaudojo novatorišką, elegantišką įrodymą, kuriuo jo kolegos stebėjosi jo paprastumu.
Atlanto Emory universiteto matematikos profesoriaus padėjėjas Hao Huangas įrodė matematinę idėją, vadinamą jautrumo spėjimu, kuri, nepaprastai grubiai tariant, pateikia teiginį apie tai, kiek galite pakeisti funkcijos įvestį nepakeisdami išvesties (tai yra jo jautrumas).
Per kelis dešimtmečius, kai matematikai pirmą kartą pasiūlė jautrumo prielaidą (to neįrodydami), teoriniai kompiuterių mokslininkai suprato, kad tai turi didžiulę reikšmę nustatant efektyviausius informacijos apdorojimo būdus.
Stebina Huango įrodymas, pasak kitų šios srities ekspertų, ne tik tai, kad Huangas jį atitraukė, bet ir elegantiškas bei aiškus būdas, kuriuo jis tai padarė. Jo įrodymas nebuvo oficialiai recenzuotas ar paskelbtas jokiame matematikos žurnale. Tačiau netrukus po to, kai Huangas paskelbė internete liepos 1 d., Jo kolegos greitai pripažino tai faktu.
„Kai tik pasirodo toks pranešimas“, - savo tinklaraštyje rašė Teksaso universiteto Ostino teorinis kompiuterių mokslų daktaras Scottas Aaronsonas, „~ 99% atvejų arba įrodymas yra neteisingas, arba bet kokiu atveju tai yra per daug sudėtinga, kad pašaliniai žmonės jį įvertintų. greitai. Tai yra vienas iš likusių 1% atvejų. Aš gana įsitikinęs, kad įrodymai yra teisingi. Kodėl? Nes aš skaičiau ir supratau. Tai man užtruko apie pusvalandį ".
Pitsburgo Carnegie Mellon universiteto numerių teoriją studijuojantis informatikos profesorius Ryanas O'Donnelis pabrėžė, kad Huango įrodymus galima apibendrinti viename tviteryje:
Ką iš tikrųjų įrodė Huangas?
Paprastumo dėlei įsivaizduokite 3D kubą, kurio kiekvienos pusės yra 1 vienetas. Jei įdėsite šį kubą į 3D koordinačių sistemą (tai reiškia, kad jis turi matavimus trimis kryptimis), vienas kampas turėtų koordinates (0,0,0), o kitas šalia jo galėtų būti (1,0,0), vienas virš jo gali būti (0,1,0) ir pan. Galite paimti pusę kampų (keturis kampus) neturėdami poros kaimynų: (0,0,0), (1,1,0), (1,0,1) ir (0,1,1) arenų nėra. t kaimynai. Galite tai parodyti pažiūrėję į kubą, bet mes taip pat tai žinome, nes visi jie skiriasi daugiau nei viena koordinate.
„Jautrumo spėlionės yra susijusios su tuo, kiek turite kaimynų, kai sugalvojate daugiau nei pusę aukštesnio matmens kubo ar hiperkaulio kampų“, - sakė Hebrajų universiteto matematikas Gil Kalai. Galite užrašyti hiperkubo koordinates kaip 1s ir 0s eilutes, kur matmenų skaičius yra eilutės ilgis, Kalai pasakojo „Live Science“. Pavyzdžiui, 4D hiperkubui yra 16 skirtingų taškų, o tai reiškia 16 skirtingų 1 ir 0 eilučių, kurios yra keturių skaitmenų ilgio.
Dabar išsirinkite pusę plius 1 atskirus taškus ant hiperkubo (4D hiperkubui tai reiškia, kad rinkitės devynis arba 8 + 1 - skirtingus taškus iš viso 16).
Iš šio mažesnio rinkinio raskite tašką su daugiausiais kaimynais - kas tai minimumas kaimynų skaičius, kurį jis gali turėti? (Kaimynai skiriasi tik vienu skaičiumi. Pavyzdžiui, 1111 ir 1110 yra kaimynai, nes norint pakeisti pirmąjį į antrą, reikia pakeisti tik vieną skaitmenį.)
Huangas įrodė, kad šiame kampe turi būti bent tiek kaimynų, kiek yra skaitmenų skaičiaus kvadratinės šaknies - šiuo atveju kvadratinės šaknies iš 4 - tai yra 2.
Jei matote mažus matmenis, tai galite pasakyti tik patikrinę. Pvz., Patikrinti kaimynuose esančias 16 koordinačių ant kubo (arba „stygų“) nėra taip sunku, pavyzdžiui. Bet kiekvieną kartą, kai pridedate matmenį prie kubo, stygų skaičius padvigubėja. Taigi labai sunku patikrinti problemą.
30 skaitmenų ilgio stygų rinkinyje - 30 matmenų kubo kampų koordinatėse - yra daugiau nei 1 milijardas skirtingų stygų, tai reiškia, kad kubas turi daugiau nei 1 milijardą kampų. Su 200 skaitmenų ilgio stygų yra daugiau nei novelmilijonų. Tai milijonas milijardų milijardų milijardų milijardų, arba 1, po kurio eina 60 nulių.
Štai kodėl matematikams patinka įrodymai: Jie parodo, kad kažkas yra tiesa visais atvejais, ne tik lengvaisiais.
„Jei n yra lygus milijonui - tai reiškia, kad turime stygas, kurių ilgis yra 1 milijonas - tada spėjama, kad jei imate 2 ^ 1 000 000-1 ir pridedate 1, tada yra eilutė, kurioje yra 1 000 kaimynų - milijono kvadratinė šaknis, „Kalai sakė.
Paskutinis svarbus jautrumo spėlionės pasiekimas įvyko 1988 m., Pasak Kalai, kai tyrėjai įrodė, kad viena eilutė turi turėti bent jau logaritmą n kaimynai. Tai daug mažesnis skaičius; 1 000 000 logaritmas yra tik 6. Taigi Huango įrodymas ką tik atrado, kad ten yra bent 994 kiti kaimynai.
Elegantiškas ir „paslaptingas“ įrodymas
„Tai labai paslaptinga“, - apie Huango įrodymą sakė Kalai. "Jis naudoja" spektrinius metodus ", kurie yra labai svarbūs metodai daugelyje matematikos sričių. Tačiau spektrinius metodus jis naudoja nauju būdu. Jis vis dar paslaptingas, bet aš manau, kad galime tikėtis, kad šis naujas būdas naudoti spektrinius metodus pamažu turės. daugiau programų “.
Iš esmės Huangas suprato hiperkubą, naudodamas skaičių masyvus eilutėse ir stulpeliuose (vadinamus matricomis). Huangas sugalvojo visiškai netikėtą būdą manipuliuoti matrica su neįprastu -1s ir 1s išdėstymu, kuris „stebuklingai priverčia visa tai veikti“, savo tinklaraštyje rašė Aaronsonas.
Huangas „paėmė šią matricą ir labai išradingai bei paslaptingai ją modifikavo“, - teigė Kalai. "Tarsi tu turi orkestrą ir jie groja muziką. Tada tu leidi kai kuriems grotuvams, aš nežinau, atsistoti ant galvos. Muzika tampa visiškai kitokia - kažkas panašaus".
Kalai teigė, kad skirtinga muzika buvo raktas įrodant spėliones. Jis sakė, kad jis paslaptingas, nes, nors matematikai supranta, kodėl metodas veikė tokiu atveju, jie nevisiškai supranta šią naują „muziką“ ar kitais atvejais, kai tai gali būti naudinga ar įdomu.
„30 metų nebuvo jokios pažangos, tada Hao Huangas išsprendė šią problemą ir rado labai paprastą įrodymą, kad atsakymas yra kvadratinė šaknis n", - sakė Kalai." Tačiau per tuos 30 metų ... žmonės suprato, kad šis klausimas yra labai svarbus skaičiavimo teorijoje. "
Kalai teigė, kad Huango įrodymas yra jaudinantis, nes pažengęs į priekį informatikos srityje. Bet tai taip pat pažymėtina, nes jis pristatė naują metodą, o matematikai vis dar nėra tikri, ką dar galėtų padėti Huano naujasis metodas.
