Matemātiķis ir atrisinājis 30 gadus vecu problēmu uz robežas starp matemātiku un datorzinātnēm. Viņš izmantoja novatorisku, elegantu pierādījumu, ar kuru viņa kolēģi brīnās par tā vienkāršību.
Hao Huangs, matemātikas profesors Emīlijas universitātē Atlantā, pierādīja matemātisku ideju, ko sauc par jutības pieņēmumu, kas neticami aptuvenā izteiksmē izsaka apgalvojumu par to, cik daudz jūs varat mainīt funkcijas ievadi, nemainot izvadi (tas ir tā jutīgums).
Gadu desmitos kopš matemātiķi pirmo reizi ierosināja jutīguma pieņēmumu (to nepierādot), teorētiskie datoru zinātnieki saprata, ka tam ir milzīga ietekme uz visefektīvāko informācijas apstrādes veidu noteikšanu.
Kas ir ievērojams attiecībā uz Huanga pierādījumiem, pēc citu nozares ekspertu domām, nav tikai tas, ka Huangs to atvilka, bet arī elegants un tiešs veids, kādā viņš to izdarīja. Viņa pierādījumi nav oficiāli pārskatīti vai publicēti nevienā matemātikas žurnālā. Bet drīz pēc tam, kad Huangs ievietoja to tiešsaistē 1. jūlijā, viņa kolēģi ātri to pieņēma kā faktu.
"Ikreiz, kad parādās šāds paziņojums," savā emuārā rakstīja Teksasas Universitātes Ostinas teorētiskais datorzinātnieks Skots Āronsons, "~ 99% laika vai nu pierādījums ir nepareizs, vai arī katrā ziņā tas ir pārāk sarežģīti, lai nepiederošie to novērtētu. ātri. Šis ir viens no atlikušajiem 1% gadījumu. Esmu diezgan pārliecināts, ka pierādījumi ir pareizi. Kāpēc? Tāpēc, ka es to lasīju un sapratu. Man vajadzēja apmēram pusstundu. "
Ryan O'Donnell, datorzinātņu profesors, kurš studē numuru teoriju Kārnegija Melona universitātē Pitsburgā, norādīja, ka Huanga pierādījumus var apkopot vienā tvītā:
Ko Huangs patiesībā pierādīja?
Vienkāršības labad iedomājieties 3D kubu ar malām, kuras katra ir 1 vienība gara. Ja jūs ievietojat šo kubu 3D koordinātu sistēmā (tas nozīmē, ka tam ir mērījumi trīs virzienos), vienam stūrim būtu koordinātas (0,0,0), otram blakus tam varētu būt (1,0,0), viens virs tā varētu būt (0,1,0) utt. Jūs varat veikt pusi no stūriem (četriem stūriem), ja nav neviena kaimiņu pāra: (0,0,0), (1,1,0), (1,0,1) un (0,1,1) aren '. t kaimiņi. To var parādīt, aplūkojot kubu, bet mēs to arī zinām, jo visi tie atšķiras vairāk nekā par vienu koordinātu.
Jutības pieņēmums ir par to, cik daudz kaimiņu jums ir, nosakot vairāk nekā pusi no augstākas dimensijas kuba vai hipera kuba stūriem, sacīja ebreju universitātes matemātiķis Gils Kalai. Jūs varat uzrakstīt hiperkuba koordinātas kā 1s un 0s virknes, kur dimensiju skaits ir virknes garums, Kalai pastāstīja Live Science. Piemēram, 4D hiperkubam ir 16 dažādi punkti, kas nozīmē 16 dažādas virknes no 1 un 0, kas ir četrus ciparus garas.
Tagad atlasiet pusi plus 1 atsevišķu punktu no hiperkuba (4D hiperkubam tas nozīmē, ka izvēlieties deviņus - vai 8 + 1 - dažādus punktus no kopumā 16).
No šī mazākā komplekta atrodiet punktu ar visvairāk kaimiņiem - kas tas ir minimums kaimiņu skaits tas var būt? (Kaimiņi atšķiras tikai ar vienu numuru. Piemēram, 1111 un 1110 ir kaimiņi, jo jums ir jāmaina tikai viens cipars, lai pirmo pārvērstu otrajā.)
Huangs pierādīja, ka šajā stūrī jābūt vismaz tikpat daudz kaimiņu, cik ir ciparu skaita kvadrātsaknei - šajā gadījumā kvadrātsaknei no 4 -, kas ir 2.
Zemu izmēru gadījumā jūs varat pateikt, ka tā ir taisnība, vienkārši pārbaudot. Nav tik grūti pārbaudīt, piemēram, 16 koordinātas uz kuba (vai "virknēm") kaimiņiem. Bet katru reizi, kad pievienojat izmēru kubam, virkņu skaits dubultojas. Tātad problēmu kļūst grūtāk ļoti ātri pārbaudīt.
Virkņu virknei, kas ir 30 ciparu gara - koordinātas 30 dimensijas kuba stūriem - tajā ir vairāk nekā 1 miljards dažādu virkņu, tas nozīmē, ka kubam ir vairāk nekā 1 miljards stūru. Ar virknēm, kuru garums ir 200 cipari, ir vairāk nekā novemdeciljons. Tas ir miljons miljardu miljardu miljardu miljardu jeb 1, kam seko 60 nulles.
Tāpēc matemātiķiem patīk pierādījumi: Tie parāda, ka kaut kas ir taisnība visos gadījumos, ne tikai vieglajos.
"Ja n ir vienāds ar miljonu - tas nozīmē, ka mums ir virknes, kuru garums ir 1 miljons -, tad tiek domāts, ka, ja ņem 2 ^ 1 000 000-1 un pievieno 1, tad ir virkne, kurai ir 1000 kaimiņu - miljona kvadrātsakne, "Kalai teica.
Pēdējais nozīmīgais jutības pieņēmuma sasniegums notika 1988. gadā, sacīja Kalai, kad pētnieki pierādīja, ka vienai virknei ir jābūt vismaz logaritmam n kaimiņi. Tas ir daudz mazāks skaits; logaritms 1 000 000 ir tikai 6. Tātad Huanga pierādījums tikko atklāja, ka tur atrodas vismaz 994 citi kaimiņi.
Elegants un "noslēpumains" pierādījums
"Tas ir ļoti noslēpumains," Kalai sacīja par Huanga pierādījumu. "Tajā tiek izmantotas" spektrālās metodes ", kas ir ļoti svarīgas metodes daudzās matemātikas jomās. Bet tas spektrālās metodes izmanto novatoriskā veidā. Tas joprojām ir noslēpumains, taču es domāju, ka mēs varam gaidīt, ka šim jaunajam spektrālo metožu izmantošanas veidam pakāpeniski būs vairāk programmu. "
Būtībā Huangs konceptualizēja hiperkubu, izmantojot skaitļu masīvus rindās un kolonnās (ko sauc par matricām). Huangs izdomāja pilnīgi negaidītu veidu, kā manipulēt ar matricu ar neparastu -1s un 1s izkārtojumu, kas "maģiski liek tam visam darboties", savā emuārā rakstīja Āronsons.
Huangs "paņēma šo matricu, un viņš to pārveidoja ļoti ģeniālā un noslēpumainā veidā", sacīja Kalai. "Tas ir tāpat kā jums ir orķestris, un viņi spēlē kādu mūziku, un tad jūs ļaujat dažiem spēlētājiem, es nezinu, stāvēt uz viņu galvas, un mūzika kļūst pavisam cita - kaut kas tāds."
Kalai sacīja, ka atšķirīgā mūzika izrādījās atslēga minējumiem. Tas ir noslēpumains, viņš teica, jo, kaut arī matemātiķi saprot, kāpēc metode darbojās šajā gadījumā, viņi pilnībā neizprot šo jauno “mūziku” vai kādos citos gadījumos tā varētu būt noderīga vai interesanta.
"30 gadus nebija nekāda progresa, un tad Hao Huangs nokārtoja šo problēmu, un viņš atrada ļoti vienkāršu pierādījumu tam, ka atbilde ir kvadrātsakne no n, "Sacīja Kalai." Bet šo 30 gadu laikā cilvēki saprata, ka šis jautājums ir ļoti svarīgs skaitļošanas teorijā. "
Huanga pierādījums ir aizraujošs, jo tas virza datorzinātnes jomu, sacīja Kalai. Bet tas ir arī ievērības cienīgs, jo ar to tika ieviesta jauna metode, un matemātiķi joprojām nav pārliecināti, ko vēl varētu atļaut Huanga jaunā metode.
