Matemaatikud lõpetavad "sfääriliste kuubikute" ehitamise

Neljandal sajandil kiitis Kreeka matemaatik Aleksandria Pappus mesilasi nende „geomeetrilise ettenägelikkuse eest”. Nende kärgstruktuuri kuusnurkne struktuur tundus olevat optimaalne viis kahemõõtmelise ruumi jaotamiseks võrdse pindala ja minimaalse perimeetriga rakkudeks – võimaldades putukatel vähendada tootmiseks vajalikku vaha ning kulutada vähem aega ja energiat oma ehitusele. taru.

Vähemalt nii oletasid Pappus ja teised. Aastatuhandete jooksul ei suutnud keegi tõestada, et kuusnurgad on optimaalsed – kuni lõpuks, 1999. aastal, näitas matemaatik Thomas Hales, et ükski teine ​​kuju ei suuda paremini toimida. Tänapäeval ei tea matemaatikud ikka veel, millised kujundid suudavad võimalikult väikese pindalaga kolme või enama dimensiooni plaatida.

Sellel "vahu" probleemil on laialdased rakendused - füüsikutele, kes uurivad seebimullide (või vahtude) käitumist ja keemikutele, kes analüüsivad kristallide struktuuri, matemaatikutele, kes uurivad sfääride pakkimise korraldusi ja statistikutele, kes töötavad välja tõhusaid andmetöötlustehnikaid. .

2000. aastate keskel jäi vahuprobleemi konkreetne sõnastus silma ka teoreetilistele arvutiteadlastele, kes avastasid üllatuseks, et see on sügavalt seotud nende valdkonna olulise lahtise probleemiga. Nad suutsid seda ühendust kasutada uue, minimaalse pinnaga kõrgmõõtmelise kuju leidmiseks.

"Mulle meeldib see edasi-tagasi sõitmine," ütles Assaf Naor Princetoni ülikoolist. “Mõni vana matemaatika muutub arvutiteaduse jaoks asjakohaseks; informaatika maksab kätte ja lahendab küsimuse matemaatikas. See on väga tore, kui see juhtub."

Kuid sellel kujul, kuigi see oli optimaalne, puudus midagi olulist: geomeetriline alus. Kuna selle olemasolu oli arvutiteaduse tehnikate abil tõestatud, oli selle tegelikku geomeetriat raske mõista. See on see, mida Naor koos Oded Regev, New Yorgi ülikooli Courant Institute'i arvutiteadlane, asus parandama eelmisel kuul veebis postitatud tõend.

"See on loole väga ilus lõpp," ütles Regev.

Kuubikujulised vahud

Matemaatikud on kaalunud vahuprobleemi muid versioone – sealhulgas seda, mis juhtub siis, kui teil on lubatud ruumi jaotada ainult täisarvu võre järgi. Ülesande selles versioonis võtate ruudukujulise massiivi ühtlaselt paigutatud punktidest (igaüks 1 ühiku kaugusel) ja muudate kõik need punktid kujundi keskpunktiks. "Kuupilise" vahu probleem küsib, milline on minimaalne pindala, kui teil on vaja ruumi sel viisil plaatida.

Teadlased olid algselt huvitatud selle piirangu kehtestamisest, et mõista topoloogiliste ruumide omadusi, mida nimetatakse kollektoriteks. Kuid küsimus sai omaette elu, muutudes oluliseks andmeanalüüsis ja muudes rakendustes.

See on ka geomeetriliselt huvitav, sest see muudab seda, mida "optimaalne" võib tähendada. Näiteks kahes mõõtmes ei saa tavalised kuusnurgad enam tasapinda paanida, kui neid saab horisontaal- ja vertikaalsuunas nihutada ainult täisarvude võrra. (Peate neid ebaratsionaalselt liigutama ühes kahest suunast.)

Ruudud võivad. Kuid kas see on parim, mida saab teha? Matemaatikuna Jaigyoung Choe avastati 1989. aastal, on vastus eitav. Optimaalne kuju on hoopis kuusnurk, mis on ühes suunas kokku surutud ja teises suunas piklik. (Sellise kuusnurga ümbermõõt on ligikaudu 3.86, kui selle pindala on 1, ületades ruudu ümbermõõtu 4.)

Need erinevused võivad tunduda triviaalsed, kuid suuremates mõõtmetes muutuvad need palju suuremaks.

Antud ruumala kõigi kujundite hulgast minimeerib pindala kera. Nagu n, mõõtmete arv, kasvab, sfääri pindala suureneb võrdeliselt ruutjuurega n.

Kuid sfäärid ei saa ruumi plaatida lünki jätmata. Seevastu an n-mõõtmeline kuubik mahuga 1 purk. Konks on selles, et selle pindala on 2n, mis kasvab otseselt proportsionaalselt selle mõõtmetega. 10,000 1-mõõtmelise kuubi ruumalaga 20,000 pindala on 400 10,000 – palju suurem kui XNUMX, mis on XNUMX XNUMX-mõõtmelise sfääri ligikaudne pindala.

Seetõttu mõtlesid teadlased, kas nad suudavad leida "sfäärilise kuubi" - kuju, mis plaaditakse n-mõõtmeline ruum, nagu kuubik, kuid mille pindala kasvab aeglaselt, nagu sfääril.

See tundus ebatõenäoline. "Kui soovite, et teie mull täidaks täpselt ruumi ja oleks selle kuubikujulise ruudustiku keskel, on raske mõelda, mida te kasutaksite peale kuupkujulise mulli," ütles ta. Ryan O'Donnell, Carnegie Melloni ülikooli teoreetiline arvutiteadlane. "Tõesti tundub, et kuubik peaks olema parim."

Nüüd teame, et see pole nii.

Raskete probleemide kõvadus

Kuubikujulise vahu probleem jäi aastakümneid suuremates mõõtmetes suhteliselt uurimata. Esimesed teadlased, kes selles edusamme tegid, ei tulnud mitte geomeetria, vaid teoreetilise arvutiteaduse valdkonnast. Nad sattusid sellele juhuslikult, otsides viisi, kuidas tõestada oma valdkonna keskset väidet unikaalsed mängud. "Unikaalne mängude oletus," ütles Regev, "on see, mida ma praegu pean teoreetilise arvutiteaduse suurimaks lahtiseks küsimuseks."

Ettepanek 2002. aastal Subhash Khot, tollal magistrant, oletab oletus, et kui konkreetset probleemi – mis hõlmab võrgu sõlmedele värvide määramist – ei saa täpselt lahendada, siis on isegi ligikaudse lahenduse leidmine väga raske. Kui see on tõsi, võimaldaks oletus teadlastel ühe hoobiga mõista paljude muude arvutusülesannete keerukust.

Arvutiteadlased liigitavad ülesandeid sageli selle järgi, kas neid saab lahendada tõhusa algoritmiga või on need hoopis "NP-rasked" (see tähendab, et neid ei saa probleemi kasvades tõhusalt lahendada seni, kuni on levinud arvamus kuid tõestamata oletus arvutusliku keerukuse kohta on tõsi). Näiteks reisiva müüja probleem, mis nõuab lühimat teed, mis on vajalik iga võrgu linna külastamiseks ainult üks kord, on NP-raske. Nii on ka selle kindlaksmääramine, kas graafi – servadega ühendatud tippude kogumit – saab märgistada maksimaalselt kolme värviga, nii et mis tahes kahel ühendatud tipul on erinevad värvid.

Selgub, et paljudele nendele ülesannetele on NP-raske leida isegi ligikaudset lahendust. Oletame, et soovite märgistada graafiku tipud erinevate värvidega viisil, mis vastab teatud piirangute loendile. Kui kõigi nende piirangute täitmine on NP-raske, siis kuidas oleks, kui prooviksite täita neist vaid 90% või 75% või 50%? Mõnest künnisest madalamal võib olla võimalik välja pakkuda tõhus algoritm, kuid sellest lävest kõrgemal muutub probleem NP-raskeks.

Arvutiteadlased on aastakümneid töötanud erinevate huvipakkuvate optimeerimisprobleemide jaoks künnised. Kuid mõned küsimused väldivad seda tüüpi kirjeldust. Kuigi algoritm võib tagada 80% parimast lahendusest, võib 95% parima lahenduse saavutamine olla NP-raske, jättes lahendamata küsimuse, kuhu täpselt 80–95% probleem NP-raskele territooriumile kaldub.

Ainulaadne mängude oletus ehk UGC pakub viisi vastuse koheseks määramiseks. See esitab väite, mis tundub esialgu piiratum: NP-raske on teha vahet graafikul, mille puhul saate täita peaaegu kõik teatud värvipiirangud (näiteks rohkem kui 99%), ja graafikul mida suudate vaevalt rahuldada (näiteks alla 1%).

Kuid vahetult pärast seda, kui 2002. aastal UGC välja pakuti, näitasid teadlased, et kui oletus vastab tõele, saate hõlpsalt arvutada kõvadusläve mis tahes piiranguga rahulolu probleemi jaoks. (Seda seetõttu, et UGC viitab ka sellele, et teadaolev algoritm saavutab kõigi nende probleemide jaoks parima võimaliku lähenduse.) "See oli just kõigi nende optimeerimisprobleemide lüli," ütles O'Donnell.

Ja nii asusid teoreetilised arvutiteadlased tõestama UGC-d - ülesannet, mis viis lõpuks mõne neist sfääriliste kuubikute avastamiseni.

Raskete probleemide raskemaks muutmine

2005. aastal töötas O’Donnell Microsoft Researchis. Tema ja kaks kolleegi — Uriel Feige, nüüd Weizmanni teadusinstituudis ja Guy Kindler, nüüd Jeruusalemma Heebrea Ülikoolis – ühines UGC-ga võitlemiseks.

Neil oli ähmane ettekujutus, kuidas nad edasi tahavad. Nad alustaksid küsimusega graafikute kohta – sellisega, mis on väga sarnane UGC-ga. Nn maksimumlõike (“max-cut”) ülesanne küsib graafiku andmisel, kuidas jagada selle tipud kaheks hulgaks (või värvideks), et neid hulki ühendavate servade arv oleks võimalikult suur. (Võite mõelda maksimaalsele lõikele kui küsimusele, kuidas on parim viis kahevärvilise graafiku värvimiseks, nii et võimalikult vähe servi ühendaks sama värvi tippe.)

Kui UGC on tõene, tähendab see, et mõne juhusliku graafiku korral võib tõhus lähendusalgoritm ulatuda selle graafiku tegelikust maksimaalsest lõikest ainult umbes 87% piiresse. Midagi paremat teha oleks NP-raske.

Feige, Kindler ja O'Donnell tahtsid hoopis vastupidises suunas minna: nad lootsid näidata, et maksimaalset lõiget on raske ligikaudselt hinnata, ja seejärel kasutada seda UGC tõestamiseks. Nende plaan toetus tehnikale, mida nimetatakse paralleelseks kordamiseks - nutikas strateegia, mis muudab rasked probleemid raskemaks.

Oletame, et tead, et on NP-raske eristada probleemi, mida saate lahendada, ja probleemi, mida saate enamasti lahendada. Paralleelne kordamine võimaldab teil sellele tuginedes näidata palju tugevamat tulemust: samuti on NP-raske eristada probleemi, mida saate lahendada, ja probleemi, mida saate vaevu üldse lahendada. "See mitteintuitiivne, sügav nähtus … on tänapäeval paljude arvutiteaduste sisemuses," ütles Naor.

Kuid seal on konks. Paralleelne kordamine ei suurenda alati probleemi tõsidust nii palju, kui arvutiteadlased seda soovivad. Eelkõige on max-cut probleemi aspekte, mis "tekitavad paralleelse kordamise jaoks suurt peavalu", ütles Regev.

Feige, Kindler ja O'Donnell keskendusid sellele, et näidata, et paralleelne kordamine võib peavalust hoolimata töötada. "See on tõesti keeruline asi, mida analüüsida," ütles Dana Moshkovitz, Austini Texase ülikooli teoreetiline arvutiteadlane. "Kuid see tundus ahvatlevalt lähedal. Näis, et paralleelne kordamine aitaks luua ühenduse maksimaalsest lõikest ainulaadsete mängudeni.

Soojenduseks püüdsid teadlased mõista paralleelset kordamist lihtsa maksimaalse lõike puhul, mida Moshkovitz nimetas "kõige rumalamaks maksimaalseks lõikeks". Kaaluge paaritu arvu tippe, mis on servadega ühendatud, et moodustada ring või "paaritu tsükkel". Soovite märgistada iga tipu ühe kahest värvist, nii et ühelgi külgnevatel tippudel poleks sama värvi. Sel juhul on see võimatu: üks serv ühendab alati sama värvi tipud. Peate selle serva kustutama, "lõhkudes" paaritu tsükli, et graafik vastaks probleemi piirangule. Lõppkokkuvõttes soovite minimeerida servade koguarvu, mille peate graafiku õigeks värvimiseks kustutama.

Paralleelne kordamine võimaldab teil kaaluda selle probleemi suuremõõtmelist versiooni - sellist, mille puhul peate katkestama kõik ilmnevad paaritu tsüklid. Feige, Kindler ja O'Donnell pidid näitama, et kuna mõõtmete arv muutub väga suureks, peate kõigi paaritute tsüklite katkestamiseks kustutama väga suure osa servadest. Kui see oleks tõsi, tähendaks see, et paralleelne kordamine võib tõhusalt võimendada selle "rumala max-cut" probleemi karedust.

Siis avastas meeskond kummalise kokkusattumuse: oli geomeetriline viis tõlgendada, kas paralleelne kordamine toimib nii, nagu nad lootsid. Saladus peitus kuubikujuliste vahtude pindalas.

Sidrunitest limonaadini

Nende probleem, mis on ümber kirjutatud vahukeeles, taandus näitamisele, et sfäärilisi kuubikuid ei saa eksisteerida – et on võimatu jagada kõrgmõõtmelist ruumi mööda täisarvvõret rakkudeks, mille pindala on palju väiksem kui kuubil. (Suurem pindala vastab vajadusele kustutada paaritute tsüklite graafikust rohkem "halbu" servi, nagu arvutiteadlased lootsid näidata.)

"Me arvasime, et oh, milline imelik geomeetriaprobleem, aga see on ilmselt tõsi, eks?" ütles O’Donnell. "Me vajasime seda tõesti, et see oleks õige vastus." Kuid tema, Feige ja Kindler ei suutnud seda tõestada. Nii et 2007. aastal avaldas raamatu kirjeldades, kuidas nad kavatsesid seda probleemi kasutada UGC ründamiseks.

Varsti nende lootused luhtusid.

Ran Raz, Princetoni teoreetiline arvutiteadlane, kes oli juba tõestanud mitmeid olulisi tulemusi paralleelse kordamise kohta, oli nende tööst huvitatud. Ta otsustas analüüsida paralleelset kordumist paaritu tsükli probleemi osas, osaliselt Feige, Kindleri ja O'Donnelli seose tõttu geomeetriaga.

Raz ei alustanud vahuprobleemiga, vaid ründas otsekohe küsimuse arvutiteaduslikku versiooni. Ta näitas, et saate vältida palju vähemate servade kustutamist, et katkestada kõik graafiku paaritu tsüklid. Teisisõnu, paralleelne kordamine ei suuda selle maksimaalse lõikeprobleemi kõvadust piisavalt võimendada. "Paralleelsest kordamisest täpselt saadavad parameetrid ei vasta sellele täpselt," ütles Moshkovitz.

"Meie plaan kasutada paralleelset kordamist ainulaadsete mängude kõvaduse näitamiseks ei töötanud isegi kõige lihtsamal juhul," ütles O'Donnell. "See rikkus kogu plaani."

Kuigi Razi tulemus oli pettumus, vihjas ka sfääriliste kuubikute olemasolu: kujundid, mis on võimelised plaatima n-mõõtmeline ruum pindalaga, mis on skaleeritud võrdeliselt ruutjuurega n. "Meil oli nii, et teeme sidrunitest limonaadi ja võtame selle pettumust valmistava tehnilise tulemuse paralleelse korduse ja diskreetsete graafikute kohta ning muudame selle geomeetrias ilusaks ja huvitavaks tulemuseks," ütles O'Donnell.

Tema ja Kindler koostöös arvutiteadlastega Anup Rao ja Avi Wigderson, uurisid Razi tõendit, kuni nad olid selle tehnikat piisavalt hästi õppinud, et need vahuprobleemiks tõlkida. 2008. aastal näitasid nad seda sfäärilised kuubikud on tõepoolest võimalikud.

"See on hea viis probleemi põhjendamiseks," ütles Mark Braverman Princetonist. "See on ilus."

Ja see tekitas küsimusi loo geomeetria poole pealt. Kuna nad kasutasid Razi töid paralleelse kordamise kohta oma plaatide kuju konstrueerimiseks, said Kindler, O’Donnell, Rao ja Wigderson midagi inetut ja Frankensteini sarnast. Plaat oli sassis ja süvendeid täis. Matemaatilises mõttes ei olnud see kumer. Kuigi see töötas nende eesmärkidel, puudusid sfäärilisel kuubil matemaatikute eelistatud omadused - omadused, mis muudavad kuju konkreetsemaks, hõlpsamini määratletavaks ja uuritavaks ning potentsiaalseteks rakendusteks sobivamaks.

"Nende ehituses on midagi väga ebarahuldavat," ütles Regev. "See näeb välja nagu amööb. See ei näe välja selline, nagu ootate, kena plaaditud korpus."

Seda ta ja Naor otsisidki.

Puurist vabanemine

Naor ja Regev mõistsid algusest peale, et nad peavad alustama nullist. "Osalt seetõttu, et kumerad kehad on nii piiravad, ei olnud ühelgi varasemal tehnikal võimalust töötada," ütles ta. Dor Minzer, Massachusettsi Tehnoloogiainstituudi teoreetiline arvutiteadlane.

Tegelikult oli täiesti usutav, et kumerus oleks liiga piirav - kumerat sfäärilist kuupi lihtsalt ei eksisteeri.

Kuid eelmisel kuul tõestasid Naor ja Regev, et saate osadeks jagada n-mõõtmeline ruum piki täisarvu koordinaate kumera kujuga, mille pindala on sfääri pindalaga üsna lähedal. Ja nad tegid seda täiesti geomeetriliselt - tagastades probleemi matemaatiliste juurte juurde.

Kõigepealt tuli neil ületada suur takistus. Kuubikujulise vahu probleem nõuab, et iga plaat oleks tsentreeritud täisarvu koordinaatidele. Kuid täisarvude võres on mõne punkti vahel väga lühike vahemaa - ja need lühikesed vahemaad põhjustavad probleeme.

Vaatleme punkti kahemõõtmelises ruudustikus. See asub horisontaal- ja vertikaalsuunas lähimatest punktidest 1 ühiku kaugusel. Kuid diagonaalsuunas on lähim punkt $latex sqrt{2}$ ühiku kaugusel – lahknevus, mis suureneb suuremates ruumides. Aastal n-dimensiooniline täisarvuvõre, lähimad punktid on endiselt 1 ühiku kaugusel, kuid need "diagonaal" punktid on nüüd $latex sqrt{n}$ ühiku kaugusel. Näiteks 10,000 100 dimensioonis tähendab see, et mis tahes punkti lähim "diagonaalne" naaber on 10,000 ühiku kaugusel, kuigi on 1 XNUMX muud punkti (üks kummaski suunas), mis on vaid XNUMX ühiku kaugusel.

Teistes võredes kasvavad need kahte tüüpi kaugused üksteisega proportsionaalselt. Matemaatikud on aastakümneid teadnud, kuidas selliseid võre plaatida minimaalse pindalaga kumera kujuga.

Kuid täisarvude võres on lühimad vahemaad alati 1. See takistab optimaalse pindalaga kena välimusega paani konstrueerimist. "Nad panid teid sellesse puuri," ütles Regev. "Nad muudavad kõik teie ümber väga tihedaks."

Nii et Naor ja Regev kaalusid selle asemel lõiku täis n-mõõtmeline ruum. Nad valisid selle alamruumi hoolikalt, et see oleks endiselt täisarvuliste punktide poolest rikas, kuid ükski neist punktidest ei oleks üksteisele liiga lähedal.

Teisisõnu, alamruum, milleni nad lõpuks jõudsid, oli just seda tüüpi, mida matemaatikud juba teadsid, kuidas optimaalselt plaatida.

Kuid see oli vaid pool tööst. Naor ja Regev pidid eraldama kogu ruumi, mitte ainult osa sellest. Et saada an n-mõõtmeline sfääriline kuubik, pidid nad oma tõhusa plaadi korrutama ülejäänud ruumist pärit paaniga (sarnaselt sellega, kuidas saate kolmemõõtmelise kuubi saamiseks korrutada kahemõõtmelise ruudu ühemõõtmelise joonelõiguga). See tõstaks nende konstruktsiooni tagasi algsesse ruumi, kuid see suurendaks ka selle pindala.

Paar pidi näitama, et ülejäänud ruumi plaat, mis ei olnud nii optimaalne, ei lisanud pinda liiga palju. Kui nad seda tegid, oli nende ehitus valmis. (Nende lõpliku kuju pindala oli veidi suurem kui mittekumera sfäärilise kuubi pindala, kuid nad usuvad, et võib olla võimalik leida kumer plaat, mis on sama tõhus kui selle mittekumera vastand.)

"Nende tõestus on täiesti erinev" varasemast sfääriliste kuubikutega seotud töödest, ütles matemaatik Noga Alon. "Ja tagantjärele mõeldes on see võib-olla loomulikum tõend. See on see, millest keegi oleks ehk pidanud proovima alustada.

"Kui asju tehakse teisiti," lisas Raz, "mõnikord leiate huvitavaid lisamõjusid."

Lootus süttis uuesti

Pole veel selge, millised need tagajärjed võivad olla – kuigi töö puudutab täisarvu võre võimalikku kasutamist krüptograafias ja muudes rakendustes. Arvestades, kuivõrd see probleem on seotud teiste valdkondadega, "viib see tõenäoliselt muude asjadeni," ütles Alon.

Hetkel arvutiteadlased ei näe võimalust kumera tulemuse tõlgendamiseks paralleelkorduse ja UGC keeles. Kuid nad ei ole täielikult loobunud esialgsest plaanist kasutada oletuse tõestamiseks vahuprobleemi. "On erinevaid viise, kuidas saate üritada õõnestada ilmselgeid tõkkeid, millega me kokku puutusime, " ütles Kindler.

Braverman ja Minzer proovisid üht sellist viisi, kui nad uuesti vaadatud vahud 2020. aastal. Selle asemel, et nõuda, et plaatide kuju oleks kumer, palusid nad, et see järgiks teatud sümmeetriat, nii et see näeks välja sama, olenemata sellest, kuidas te selle koordinaate pöörate. (2D-s ruut toimiks, kuid ristkülik mitte; mitte ka seni kirjeldatud suuremõõtmelised sfäärilised kuubikud.) Selle uue piirangu kohaselt suutis paar näidata seda, mida Kindler ja teised lootsid 15 aastat varem: et kuubi pindalast ei saa ju palju paremat teha.

See vastas teistsugusele paralleelsele kordusele – sellisele, mis muudaks lihtsaima maksimaalse lõike nii kõvaks kui vaja. Kuigi tulemus pakub selle uurimissuuna jaoks lootust, pole selge, kas see paralleelse korduse versioon töötab kõigi maksimaalsete probleemide korral. "See ei tähenda, et olete lõpetanud," ütles Braverman. "See tähendab lihtsalt, et olete tagasi äris."

"Geomeetrias on palju potentsiaali, " ütles Minzer. "Me lihtsalt ei mõista seda piisavalt."