Matematiki dokončali nalogo za izgradnjo "sferičnih kock"

V četrtem stoletju je grški matematik Papus iz Aleksandrije hvalil čebele zaradi njihove »geometrične premišljenosti«. Šestkotna struktura njihovega satja se je zdela kot optimalen način za razdelitev dvodimenzionalnega prostora na celice enake površine in minimalnega obsega, kar je žuželkam omogočilo, da zmanjšajo količino voska, ki ga potrebujejo za proizvodnjo, ter porabijo manj časa in energije za gradnjo svojih panj.

Ali tako so domnevali Pappus in drugi. Tisočletja nihče ni mogel dokazati, da so šesterokotniki optimalni - dokler končno leta 1999 matematik Thomas Hales ni pokazal, da nobena druga oblika ne more biti boljša. Danes matematiki še vedno ne vedo, s katerimi oblikami lahko pokrijemo tri ali več dimenzij z najmanjšo možno površino.

Izkazalo se je, da ima ta problem "pene" široko paleto aplikacij - za fizike, ki preučujejo obnašanje milnih mehurčkov (ali pen), in kemike, ki analizirajo strukturo kristalov, za matematike, ki raziskujejo ureditve pakiranja sfer, in statistike, ki razvijajo učinkovite tehnike obdelave podatkov. .

Sredi 2000-ih je posebna formulacija problema pene padla v oči tudi teoretičnim računalniškim znanstvenikom, ki so na svoje presenečenje ugotovili, da je globoko povezana s pomembnim odprtim problemom na njihovem področju. To povezavo so lahko uporabili, da bi našli novo visokodimenzionalno obliko minimalne površine.

"Obožujem to naprej in nazaj," je rekel Assaf Naor univerze Princeton. »Nekatera stara matematika postane pomembna za računalništvo; računalništvo povrne in reši vprašanje v matematiki. Zelo lepo je, ko se to zgodi.”

Toda tej obliki, čeprav optimalni, je manjkalo nekaj pomembnega: geometrijski temelj. Ker je bil njegov obstoj dokazan s tehnikami iz računalništva, je bilo težko razumeti njegovo dejansko geometrijo. To je tisto, kar Naor, skupaj z Oded Regev, računalniški znanstvenik na inštitutu Courant na univerzi v New Yorku, se je odločil popraviti dokazilo, objavljeno na spletu prejšnji mesec.

"To je zelo lep konec zgodbe," je dejal Regev.

Kubične pene

Matematiki so razmišljali o drugih različicah problema s peno - vključno s tem, kaj se zgodi, če vam je dovoljeno razdeliti prostor samo glede na tako imenovano mrežo celih števil. V tej različici problema vzamete kvadratni niz enakomerno razporejenih točk (vsaka 1 enota narazen) in vsako od teh točk postavite v središče oblike. Problem "kubične" pene se sprašuje, kakšna bo minimalna površina, ko boste morali prostor obložiti na ta način.

Raziskovalce je sprva zanimala uvedba te omejitve, da bi razumeli lastnosti topoloških prostorov, imenovanih mnogoterosti. Toda vprašanje je zaživelo svoje življenje in postalo pomembno pri analizi podatkov in drugih aplikacijah.

Prav tako je geometrično zanimivo, ker spremeni, kaj bi lahko pomenilo "optimalno". V dveh dimenzijah, na primer, pravilni šesterokotniki ne morejo več poravnati ravnine, če jih je mogoče premakniti le za celo število v vodoravni in navpični smeri. (Morate jih premakniti v neracionalnih količinah v eno od obeh smeri.)

Kvadrati lahko. Toda ali je to najboljše, kar je mogoče narediti? Kot matematik Jaigyoung Choe odkrit leta 1989, je odgovor ne. Optimalna oblika je šesterokotnik, ki je stisnjen v eno smer in podaljšan v drugo. (Obseg takšnega šesterokotnika je približno 3.86, če je njegova ploščina 1 – presega obseg kvadrata 4.)

Te razlike se morda zdijo nepomembne, vendar so v višjih dimenzijah veliko večje.

Med vsemi oblikami določene prostornine je tista, ki zmanjša površino, krogla. Kot n, število dimenzij, raste, površina krogle se povečuje sorazmerno s kvadratnim korenom n.

Toda krogle ne morejo obložiti prostora, ne da bi pustile vrzeli. Po drugi strani pa an n-dimenzionalna kocka prostornine 1 pločevinka. Ulov je v tem, da je njegova površina 2n, ki raste premosorazmerno s svojo dimenzijo. 10,000-dimenzionalna kocka prostornine 1 ima površino 20,000 — veliko večjo od 400, kar je približno površina 10,000-dimenzionalne krogle.

In tako so se raziskovalci spraševali, ali bi lahko našli "sferično kocko" - obliko, ki je ploščica n-dimenzionalni prostor, kot je kocka, vendar njegova površina počasi raste, kot je krogla.

Zdelo se je malo verjetno. "Če želite, da vaš mehurček natančno zapolni prostor in je osredotočen na to kubično mrežo, je težko razmišljati o tem, kaj bi uporabili razen kubičnega mehurčka," je dejal Ryan O'Donnell, teoretični računalniški znanstvenik na univerzi Carnegie Mellon. "Res se zdi, da bi morala biti kocka najboljša."

Zdaj vemo, da ni.

Trdota težkih problemov

Desetletja je bil problem kubične pene razmeroma neraziskan v višjih dimenzijah. Prvi raziskovalci, ki so napredovali na tem področju, niso prišli s področja geometrije, ampak iz teoretičnega računalništva. Nanjo so naleteli po naključju, ko so iskali način, kako dokazati osrednjo trditev na svojem področju, znano kot domneva o edinstvenih igrah. "Edinstvena domneva o igrah," je dejal Regev, "je trenutno največje odprto vprašanje v teoretični računalniški znanosti."

Leta 2002 predlagal Subhash Khot, takrat podiplomskega študenta, domneva, da če določenega problema – tistega, ki vključuje dodeljevanje barv vozliščem omrežja – ni mogoče natančno rešiti, je iskanje celo približne rešitve zelo težko. Če je resnična, bi domneva raziskovalcem omogočila, da naenkrat razumejo kompleksnost široke palete drugih računalniških nalog.

Računalniški znanstveniki naloge pogosto razvrščajo glede na to, ali jih je mogoče rešiti z učinkovitim algoritmom ali pa so namesto tega »NP-težke« (kar pomeni, da jih ni mogoče učinkovito rešiti, ko se velikost problema povečuje, dokler se splošno verjame, vendar je nedokazana domneva o računski kompleksnosti resnična). Na primer, problem potujočega prodajalca, ki zahteva najkrajšo pot, potrebno za obisk vsakega mesta v omrežju samo enkrat, je NP-težek. Enako velja za ugotavljanje, ali je graf – zbirko tock, povezanih z robovi – mogoče označiti z največ tremi barvami, tako da imata kateri koli dve povezani točki različni barvi.

Izkazalo se je, da je NP-težko najti celo približno rešitev za mnoge od teh nalog. Recimo, da želite označiti vozlišča grafa z različnimi barvami na način, ki ustreza nekemu seznamu omejitev. Če je NP-težko zadovoljiti vse te omejitve, kaj pa če bi poskušali izpolniti le 90 %, ali 75 %, ali 50 %? Pod določenim pragom je morda mogoče najti učinkovit algoritem, nad tem pragom pa postane težava NP-težka.

Desetletja so si računalniški znanstveniki prizadevali določiti pragove za različne težave optimizacije. Toda nekatera vprašanja se izmikajo tovrstnemu opisu. Medtem ko lahko algoritem jamči 80 % najboljše rešitve, je morda NP-težko doseči 95 % najboljše rešitve, pri čemer ostane nerešeno vprašanje, kje točno med 80 % in 95 % se težava nagiba na NP-trdo ozemlje.

Edinstvena domneva o igrah ali UGC ponuja način za takojšnjo določitev odgovora. Poda izjavo, ki se sprva zdi bolj omejena: da je NP-težko ugotoviti razliko med grafom, za katerega lahko zadostite skoraj vsem določenim nizom barvnih omejitev (recimo več kot 99 %), in grafom za ki jih lahko zadovoljite komaj kaj (recimo manj kot 1%).

Toda kmalu po tem, ko je bil leta 2002 predlagan UGC, so raziskovalci pokazali, da če je domneva resnična, potem lahko zlahka izračunate prag trdote za kakršen koli problem zadovoljevanja omejitev. (To je zato, ker UGC prav tako implicira, da znani algoritem doseže najboljši možni približek za vse te probleme.) "Prav to je bil temelj vseh teh problemov optimizacije," je dejal O'Donnell.

In tako so se teoretični računalniški znanstveniki odločili dokazati UGC – naloga, zaradi katere so nekateri na koncu odkrili sferične kocke.

Oteževanje težav

Leta 2005 je O'Donnell delal pri Microsoft Research. On in dva kolega - Uriel Feige, zdaj na Weizmannovem inštitutu za znanost, in Guy Kindler, zdaj na Hebrejski univerzi v Jeruzalemu — združil moči, da bi se spopadel z UGC.

Imeli so nejasno predstavo o tem, kako želijo nadaljevati. Začeli bi z vprašanjem o grafih, ki je zelo podoben UGC. Tako imenovani problem največjega reza (»max-cut«) sprašuje, ko dobimo graf, kako razdeliti njegova oglišča na dva niza (ali barve), tako da je število robov, ki povezujejo te nize, čim večje. (Maksimalni rez si lahko predstavljate kot vprašanje o najboljšem načinu za barvanje grafa z dvema barvama, tako da čim manj robov povezuje vozlišča iste barve.)

Če je UGC resničen, bi to pomenilo, da lahko učinkoviti algoritem približevanja glede na nek naključni graf doseže le približno 87 % resničnega največjega reza tega grafa. Narediti kaj boljšega bi bilo NP-težko.

Feige, Kindler in O'Donnell so namesto tega želeli iti v nasprotno smer: upali so, da bodo pokazali, da je največje zmanjšanje težko približati, in nato to uporabili za dokaz UGC. Njihov načrt se je zanašal na moč tehnike, imenovane vzporedno ponavljanje - pametna strategija, ki težke probleme oteži.

Recimo, da veste, da je NP-težko razlikovati med problemom, ki ga lahko rešite, in tistim, ki ga večinoma lahko rešite. Vzporedno ponavljanje vam omogoča, da gradite na tem, da pokažete veliko močnejši rezultat trdote: da je tudi NP-težko razlikovati med problemom, ki ga lahko rešite, in tistim, ki ga komajda rešite. "Ta neintuitiven, globok pojav ... je danes v drobovju številnih računalniških znanosti," je dejal Naor.

Vendar obstaja ulov. Vzporedno ponavljanje ne poveča vedno trdote problema toliko, kot si računalničarji želijo. Predvsem obstajajo vidiki problema največjega zmanjšanja, ki "ustvarjajo velik glavobol pri vzporednem ponavljanju," je dejal Regev.

Feige, Kindler in O'Donnell so se osredotočili na prikaz, da lahko vzporedno ponavljanje deluje kljub glavobolom. "To je res zapletena stvar za analizo," je dejal Dana Moshkovitz, teoretični računalniški znanstvenik na Univerzi v Teksasu v Austinu. »Toda to se je zdelo mamljivo blizu. Zdelo se je, da bo vzporedno ponavljanje [pomagalo vzpostaviti] to povezavo od največjega zmanjšanja do edinstvenih iger.«

Za ogrevanje so raziskovalci poskušali razumeti vzporedno ponavljanje za preprost primer največjega zmanjšanja, kar je Moshkovitz imenoval "najbolj neumno največje zmanjšanje." Razmislite o lihem številu vozlišč, povezanih z robovi, da tvorijo krog ali "neparen cikel". Vsako točko želite označiti z eno od dveh barv, tako da noben par sosednjih tock nima enake barve. V tem primeru je to nemogoče: En rob bo vedno povezoval oglišča iste barve. Ta rob morate izbrisati in "prekiniti" nenavaden cikel, da bo vaš graf zadostil omejitvi problema. Navsezadnje želite čim bolj zmanjšati skupni delež robov, ki jih morate izbrisati, da pravilno obarvate svoj graf.

Vzporedno ponavljanje vam omogoča, da razmislite o visokodimenzionalni različici te težave - tisti, v kateri morate prekiniti vse nenavadne cikle, ki se pojavijo. Feige, Kindler in O'Donnell so morali pokazati, da morate, ko se število dimenzij zelo poveča, izbrisati zelo velik del robov, da prekinete vse nenavadne cikle. Če bi bilo to res, bi to pomenilo, da bi vzporedno ponavljanje lahko učinkovito povečalo trdoto tega problema "neumnega maksimalnega rezanja".

Takrat je ekipa odkrila nenavadno naključje: obstajal je geometrijski način za razlago, ali bo vzporedno ponavljanje delovalo tako, kot so upali. Skrivnost je bila v površini kubičnih pen.

Od limon do limonade

Njihov problem, prepisan v jeziku pen, se je zmanjšal na to, da pokažejo, da sferične kocke ne morejo obstajati - da je nemogoče razdeliti visokodimenzionalni prostor vzdolž mreže celih števil na celice s površino, veliko manjšo od površine kocke. (Večja površina ustreza potrebi po brisanju več "slabih" robov v grafu lihih ciklov, kot so računalničarji upali pokazati.)

"Bili smo kot, oh, kakšen čuden geometrijski problem, ampak to je verjetno res, kajne?" je rekel O'Donnell. "To smo res potrebovali, da bi bil pravi odgovor." Toda on, Feige in Kindler tega niso mogli dokazati. Tako so leta 2007 objavil prispevek ki opisujejo, kako so nameravali uporabiti to težavo za napad na UGC.

Kmalu so bili njihovi upi razblinjeni.

Ran Raz, teoretični računalniški znanstvenik na Princetonu, ki je že dokazal več pomembnih rezultatov o vzporednem ponavljanju, je bil navdušen nad njunim člankom. Odločil se je analizirati vzporedno ponavljanje za problem neparnega cikla, deloma zaradi povezave z geometrijo, ki so jo odkrili Feige, Kindler in O'Donnell.

Raz ni začel s problemom pene, ampak je neposredno napadel računalniško različico vprašanja. Pokazal je, da se lahko izognete brisanju veliko manj robov, da prekinete vse nenavadne cikle v grafu. Z drugimi besedami, vzporedno ponavljanje ne more dovolj povečati trdote tega problema maksimalnega reza. "Parametri, ki jih dobimo z vzporednim ponavljanjem natančno, natančno ne dosegajo tega," je dejal Moshkovitz.

"Naš načrt za uporabo vzporednega ponavljanja za prikaz trdote edinstvenih iger ni deloval niti v najpreprostejšem primeru," je dejal O'Donnell. "To je pokvarilo celoten načrt."

Čeprav razočaranje, je Razov rezultat tudi namigoval na obstoj sferičnih kock: oblik, ki jih je mogoče polagati v ploščice. n-dimenzionalni prostor s površino, ki se spreminja sorazmerno s kvadratnim korenom n. »Mislili smo, da naredimo limonado iz limon in vzamemo ta razočarani tehnični rezultat o vzporednem ponavljanju in diskretnih grafih ter ga spremenimo v čeden, zanimiv rezultat v geometriji,« je dejal O'Donnell.

On in Kindler, v sodelovanju z računalničarji Anup Rao in Avi Wigderson, preučili Razov dokaz, dokler se njegovih tehnik niso dovolj dobro naučili, da bi jih prenesli na problem pene. Leta 2008 so to tudi pokazali sferične kocke so res možne.

"To je lep način za razmišljanje o težavi," je rekel Mark Braverman iz Princetona. "Lepo je."

In sprožil je vprašanja o geometrijski strani zgodbe. Kindler, O'Donnell, Rao in Wigderson so, ker so uporabili Razovo delo pri vzporednem ponavljanju, da bi zgradili svojo obliko ploščic, dobili nekaj grdega in Frankensteinovega. Ploščica je bila neurejena in polna vdolbin. V matematičnem smislu ni bil konveksen. Čeprav je to delovalo za njihove namene, je sferični kocki manjkalo lastnosti, ki jih imajo matematiki raje - lastnosti, zaradi katerih je oblika bolj konkretna, lažja za definiranje in preučevanje ter bolj primerna za morebitne aplikacije.

"V njihovi konstrukciji je nekaj zelo nezadovoljivega," je dejal Regev. »Videti je kot ameba. Ni videti tako, kot bi pričakovali, lepo ohišje s ploščicami.”

To sta se z Naorom namenila iskat.

Osvoboditev iz kletke

Naor in Regev sta se že na začetku zavedala, da bosta morala začeti iz nič. "Delno zato, ker so konveksna telesa tako restriktivna, nobena od prejšnjih tehnik ni imela nobene možnosti za delovanje," je dejal Dor Minzer, teoretični računalniški znanstvenik na tehnološkem inštitutu Massachusetts.

Pravzaprav je bilo povsem verjetno, da bi bila konveksnost preveč omejevalna - da konveksna sferična kocka preprosto ne obstaja.

Toda prejšnji mesec sta Naor in Regev dokazala, da lahko deliš n-dimenzionalni prostor vzdolž celih koordinat s konveksno obliko, katere površina je precej blizu površine krogle. In to so storili povsem geometrijsko - problem so vrnili k njegovim matematičnim koreninam.

Najprej so morali obiti veliko oviro. Problem kubične pene zahteva, da je vsaka ploščica centrirana na celoštevilske koordinate. Toda v celoštevilski mreži so zelo kratke razdalje med nekaterimi točkami - in te kratke razdalje povzročajo težave.

Razmislite o točki v dvodimenzionalni mreži. Nahaja se 1 enoto stran od svojih najbližjih točk v vodoravni in navpični smeri. Toda v diagonalni smeri je najbližja točka oddaljena $latex sqrt{2}$ enot – razlika, ki se v večjih prostorih še poslabša. V n-dimenzionalno celoštevilsko mrežo, so najbližje točke še vedno oddaljene 1 enoto, vendar so te "diagonalne" točke zdaj oddaljene $latex sqrt{n}$ enot. V, recimo, 10,000 dimenzijah to pomeni, da je najbližji "diagonalni" sosed katere koli točke oddaljen 100 enot, čeprav obstaja 10,000 drugih točk (po ena v vsako smer), ki so oddaljene samo 1 enoto.

V drugih mrežah ti dve vrsti razdalj rasteta sorazmerno ena z drugo. Matematiki že desetletja vedo, kako obložiti takšne mreže s konveksnimi oblikami minimalne površine.

Toda v celoštevilski mreži bodo najkrajše razdalje vedno obtičale pri 1. To ovira gradnjo lepe ploščice z optimalno površino. "Nekako so te dali v to kletko," je rekel Regev. "Vse okoli tebe naredijo zelo tesno."

Tako sta Naor in Regev namesto tega upoštevala del polnega n-dimenzionalni prostor. Ta podprostor so skrbno izbrali, tako da bi bil še vedno bogat s celimi točkami, vendar nobena od teh točk ne bi bila preblizu skupaj.

Z drugimi besedami, podprostor, ki so ga dobili, je bil natanko tisti tip, ki so ga matematiki že znali optimalno razporediti.

Toda to je bilo le pol dela. Naor in Regev sta morala pregraditi ves prostor, ne le delček. Da bi dobili n-dimenzionalno sferično kocko, so morali svojo učinkovito ploščico pomnožiti s ploščico iz preostalega prostora (podobno, kot bi lahko pomnožili dvodimenzionalni kvadrat z enodimenzionalno črto, da bi dobili tridimenzionalno kocko). S tem bi njihovo konstrukcijo dvignili nazaj v prvotni prostor, a bi tudi povečali njeno površino.

Par je moral pokazati, da ploščica iz preostalega prostora, ki ni bil tako optimalen, ne doda preveč k površini. Ko so to storili, je bila njihova gradnja končana. (Površina njihove končne oblike je bila nekoliko večja od površine nekonveksne sferične kocke, vendar menijo, da bi bilo mogoče najti konveksno ploščico, ki bi bila prav tako učinkovita kot njena nekonveksna dvojnica.)

"Njihov dokaz je popolnoma drugačen" od prejšnjega dela na sferičnih kockah, je dejal matematik Noga Alon. »In retrospektivno je to morda bolj naraven dokaz. To je tisto, kar bi nekdo morda moral poskusiti začeti.«

"Ko se stvari naredijo drugače," je dodal Raz, "včasih najdete zanimive dodatne implikacije."

Opet upanje

Ni še jasno, kakšne bi lahko bile te posledice - čeprav se delo dotika potencialne uporabe celoštevilskih mrež v kriptografiji in drugih aplikacijah. Glede na to, kako povezana je ta težava z drugimi področji, bo verjetno vodila do drugih stvari, je dejal Alon.

Trenutno računalniški znanstveniki ne vidijo načina za razlago konveksnega rezultata v jeziku vzporednega ponavljanja in UGC. Niso pa povsem opustili prvotnega načrta, da bi problem s peno uporabili za dokaz domneve. "Obstajajo različni načini, kako lahko poskusite spodkopati očitne ovire, na katere smo naleteli," je dejal Kindler.

Braverman in Minzer sta poskusila en tak način, ko sta leta 2020 ponovno pregledane pene. Namesto da bi zahtevali, da je oblika ploščice konveksna, so zahtevali, da upošteva določene simetrije, tako da je videti enako, ne glede na to, kako obrnete njene koordinate. (V 2D bi kvadrat deloval, pravokotnik pa ne; prav tako ne bi bile visokodimenzionalne sferične kocke, opisane do danes.) Pod to novo omejitvijo je paru uspelo pokazati, kar so Kindler in drugi upali pred 15 leti: da navsezadnje ne moreš narediti veliko bolje od površine kocke.

To je ustrezalo drugačni vrsti vzporednega ponavljanja – takšnemu, ki bi naredil najpreprostejši primer maksimalnega rezanja tako močnega, kot bi moral biti. Medtem ko rezultat ponuja nekaj upanja za to linijo raziskav, ni jasno, ali bo ta različica vzporednega ponavljanja delovala pri vseh težavah z največjim rezom. "To ne pomeni, da ste končali," je dejal Braverman. "To samo pomeni, da ste spet v poslu."

"V geometriji je veliko potenciala," je dejal Minzer. "Samo tega ne razumemo dovolj dobro."