A matematikusok teljesítik a küldetést, hogy „gömbkockákat” építsenek

A negyedik században az alexandriai Pappus görög matematikus dicsérte a méheket „geometriai előrelátásukért”. Méhsejtjeik hatszögletű felépítése az optimális módszernek tűnt a kétdimenziós tér egyenlő területű és minimális kerületű sejtekre való felosztására – lehetővé téve a rovarok számára, hogy csökkentsék a termeléshez szükséges viasz mennyiségét, és kevesebb időt és energiát fordítsanak saját maguk építésére. kaptár.

Legalábbis Pappus és mások ezt feltételezték. Évezredeken keresztül senki sem tudta bizonyítani, hogy a hatszögek optimálisak – míg végül 1999-ben Thomas Hales matematikus bebizonyította, hogy nincs más alakzat jobb. Ma a matematikusok még mindig nem tudják, mely formák képesek három vagy több dimenziót a lehető legkisebb felülettel csempézni.

Kiderült, hogy ennek a „hab” problémának széles körű alkalmazásai vannak – a szappanbuborékok (vagy habok) viselkedését tanulmányozó fizikusok és a kristályok szerkezetét elemző kémikusok, a gömbcsomagolási elrendezéseket kutató matematikusok és a hatékony adatfeldolgozási technikákat kidolgozó statisztikusok számára. .

A 2000-es évek közepén a habprobléma egy sajátos megfogalmazása felkeltette az elméleti informatikusok figyelmét, akik meglepetésükre felfedezték, hogy ez szorosan kapcsolódik egy fontos nyitott problémához a szakterületükön. Felhasználhatták ezt a kapcsolatot, hogy új, nagy dimenziós formát találjanak minimális felülettel.

„Imádom ezt az oda-vissza valót” – mondta Assaf Naor a Princetoni Egyetemen. „Néhány régi matematika relevánssá válik az informatika számára; az informatika megtérül és matematikában megoldja a kérdést. Nagyon jó, amikor ez megtörténik.”

De ebből a formából, bár optimális, hiányzott valami fontos: egy geometriai alap. Mivel létezését számítástechnikai technikákkal bizonyították, tényleges geometriáját nehéz volt felfogni. Naor ezzel együtt Oded Regev, a New York-i Egyetem Courant Intézetének informatikusa arra vállalkozott, hogy kijavítsa a múlt hónapban online közzétett bizonyíték.

„Nagyon szép vége a történetnek” – mondta Regev.

Kocka alakú habok

A matematikusok a habprobléma más változatait is fontolgatták – beleértve azt is, hogy mi történik, ha csak az úgynevezett egészrács szerint szabad partícionálni a teret. A feladatnak ebben a verziójában egyenlő távolságra lévő pontokból álló négyzettömböt vesz (mindegyik 1 egységnyi távolságra), és mindegyik pontot egy alakzat középpontjává teszi. A „kocka alakú” hab probléma azt kérdezi, hogy mekkora lesz a minimális felület, amikor ilyen módon kell teret burkolni.

A kutatók kezdetben a korlátozás bevezetése iránt érdeklődtek, hogy megértsék a sokaságnak nevezett topológiai terek tulajdonságait. A kérdés azonban önálló életre kelt, és relevánssá vált az adatelemzésben és más alkalmazásokban.

Geometriailag is érdekes, mert megváltoztatja, mit jelenthet az „optimális”. Két dimenzióban például a szabályos hatszögek már nem tudják mozaikkázni a síkot, ha csak egész számokkal mozgathatók vízszintes és függőleges irányban. (Irracionális mértékkel kell mozgatni őket a két irány valamelyikébe.)

Négyzetek is. De vajon ez a legjobb, amit tehetünk? Mint a matematikus Jaigyoung Choe 1989-ben fedezték fel, a válasz nem. Az optimális forma ehelyett egy hatszög, amelyet az egyik irányban összenyomtak, a másikban megnyúltak. (Egy ilyen hatszög kerülete hozzávetőlegesen 3.86, ha területe 1 – felülmúlva a négyzet 4-es kerületét.)

Ezek a különbségek triviálisnak tűnhetnek, de magasabb dimenziókban sokkal nagyobbak.

Egy adott térfogat összes alakja közül az, amelyik minimalizálja a felületet, a gömb. Mint n, a méretek száma nő, a gömb felülete a négyzetgyökével arányosan nő n.

De a gömbök nem tudnak teret csempézni anélkül, hogy hézagokat hagynának. Másrészt egy n-dimenziós kocka térfogata 1 kanna. A lényeg, hogy felülete 2n, méretével egyenes arányban növekszik. Egy 10,000. térfogatú 1 20,000 dimenziós kocka felülete 400 10,000 – sokkal nagyobb, mint XNUMX, ami egy XNUMX XNUMX dimenziós gömb hozzávetőleges felülete.

Ezért a kutatók azon töprengtek, vajon sikerül-e találniuk egy „gömb alakú kockát” – egy olyan formát, amely csempézik n-dimenziós tér, mint egy kocka, de a felülete lassan növekszik, mint egy gömbé.

Valószínűtlennek tűnt. „Ha azt szeretné, hogy a buborék pontosan kitöltse a teret, és ennek a kocka alakú rácsnak a középpontjában álljon, nehéz elképzelni, mit használna, kivéve egy kocka alakú buborékot” – mondta. Ryan O'Donnell, a Carnegie Mellon Egyetem elméleti informatikusa. "Valóban úgy tűnik, hogy a kockának kell a legjobbnak lennie."

Most már tudjuk, hogy nem.

A nehéz problémák keménysége

Évtizedekig a kocka alakú hab probléma viszonylag feltáratlan volt nagyobb méretekben. Az első kutatók, akik előrehaladást értek el ezen, nem a geometria, hanem az elméleti számítástechnika területéről érkeztek. Véletlenül bukkantak rá, miközben keresték a módját, hogy bebizonyítsák egy központi állítást a szakterületükön, az úgynevezett egyedi játékok sejtése. „Az egyedülálló játékokra vonatkozó sejtés – mondta Regev – az, amit jelenleg az elméleti számítástechnika legnagyobb nyitott kérdésének tartok.

2002-ban javasolta Subhash Khot, egy akkori végzős hallgató, a sejtés azt feltételezi, hogy ha egy adott probléma – amely a hálózat csomópontjaihoz színek hozzárendelésével jár – nem oldható meg pontosan, akkor még hozzávetőleges megoldást is nagyon nehéz találni. Ha igaz, a sejtés lehetővé tenné a kutatók számára, hogy egy csapásra megértsék az egyéb számítási feladatok hatalmas választékának összetettségét.

Az informatikusok gyakran az alapján osztályozzák a feladatokat, hogy megoldhatók-e egy hatékony algoritmussal, vagy inkább „NP-nehezek” (ami azt jelenti, hogy nem lehet hatékonyan megoldani a probléma méretének növekedésével mindaddig, amíg széles körben elterjedt a vélemény de igazak a számítási bonyolultságról szóló bizonyítatlan sejtések). Például az utazó értékesítő probléma, amely a hálózat minden városának meglátogatásához szükséges legrövidebb utat kéri, NP-nehéz. Ugyanígy annak meghatározása is, hogy egy gráf – élekkel összekapcsolt csúcsok gyűjteménye – legfeljebb három színnel címkézhető-e úgy, hogy bármely két összekapcsolt csúcs eltérő színű legyen.

Kiderült, hogy sok ilyen feladatra NP-nehéz még hozzávetőleges megoldást is találni. Tegyük fel, hogy egy gráf csúcsait különböző színekkel szeretné felcímkézni oly módon, hogy az megfeleljen a korlátozások bizonyos listájának. Ha NP-nehéz teljesíteni az összes megszorítást, mi van azzal, ha megpróbáljuk csak 90%-ukat, 75%-át vagy 50%-át teljesíteni? Valamilyen küszöb alatt lehet, hogy ki lehet találni egy hatékony algoritmust, de e küszöb felett a probléma NP-nehéz lesz.

Az informatikusok évtizedek óta dolgoznak azon, hogy leszögezzék a küszöböket a különböző érdeklődésre számot tartó optimalizálási problémákhoz. Néhány kérdés azonban elkerüli ezt a fajta leírást. Míg egy algoritmus garantálhatja a legjobb megoldás 80%-át, lehet, hogy NP-nehéz elérni a legjobb megoldás 95%-át, így eldöntetlen marad a kérdés, hogy a probléma 80% és 95% között pontosan hol csúszik az NP-nehéz területre.

Az egyedülálló játéksejtés vagy az UGC lehetőséget kínál a válasz azonnali meghatározására. Olyan kijelentést tesz, amely elsőre korlátozottabbnak tűnik: NP-nehéz különbséget tenni egy olyan grafikon között, amelyre a színezési megkötések szinte minden halmaza megfelel (mondjuk több mint 99%), és egy olyan gráf között, amelyet alig tudsz kielégíteni (mondjuk 1%-nál kevesebbet).

Nem sokkal azután, hogy az UGC-t 2002-ben javasolták, a kutatók kimutatták, hogy ha a sejtés igaz, akkor könnyen kiszámítható a keménységi küszöb bármely korlát-elégedettségi probléma esetén. (Ez azért van, mert az UGC azt is jelenti, hogy egy ismert algoritmus a lehető legjobb közelítést éri el mindezen problémák esetén.) „Pontosan ez volt az összes optimalizálási probléma kulcsa” – mondta O'Donnell.

Így hát az elméleti informatikusok nekiálltak bizonyítani az UGC-t – ez a feladat végül arra késztetett néhányukat, hogy felfedezzék a gömbkockákat.

A nehéz problémák megnehezítése

2005-ben O'Donnell a Microsoft Researchnél dolgozott. Ő és két kollégája – Uriel Feige, most a Weizmann Tudományos Intézetben, és Guy Kindler, jelenleg a jeruzsálemi Héber Egyetemen – összefogtak az UGC leküzdésére.

Halvány fogalmuk volt arról, hogyan akarnak továbbmenni. A grafikonokkal kapcsolatos kérdéssel kezdenének – egy olyan kérdéssel, amely nagyon hasonlít az UGC-hez. Az úgynevezett maximum vágás („max-cut”) probléma azt kérdezi, hogy ha adott gráfnak, hogyan lehet annak csúcsait két halmazra (vagy színre) felosztani úgy, hogy a halmazokat összekötő élek száma a lehető legnagyobb legyen. (A max. vágást úgy is felfoghatjuk, mint azt a kérdést, hogy hogyan lehet a legjobban színezni egy gráfot két színnel, hogy minél kevesebb él kössön azonos színű csúcsokat.)

Ha az UGC igaz, az azt jelentené, hogy valamilyen véletlen gráf esetén egy hatékony közelítő algoritmus csak a gráf valódi maximális metszésének körülbelül 87%-án belül tud elférni. Jobbat csinálni NP-nehéz lenne.

Feige, Kindler és O'Donnell ehelyett az ellenkező irányba akartak menni: azt remélték, hogy megmutatják, hogy a maximális vágást nehéz közelíteni, majd ezt felhasználják az UGC bizonyítására. Tervük a párhuzamos ismétlésnek nevezett technika erején alapult – egy okos stratégia, amely megnehezíti a nehéz problémákat.

Tegyük fel, hogy tudja, hogy NP-nehéz különbséget tenni a megoldható és a többnyire megoldható probléma között. A párhuzamos ismétlés lehetővé teszi, hogy erre építve sokkal erősebb keménységi eredményt mutassunk: azt is, hogy NP-nehéz különbséget tenni a megoldható és az alig megoldható probléma között. „Ez a nem intuitív, mély jelenség… ma sok számítástechnika zsigerében van” – mondta Naor.

De van egy fogás. A párhuzamos ismétlés nem mindig erősíti fel annyira a probléma keménységét, mint ahogy azt az informatikusok szeretnék. Különösen a max-cut problémának vannak olyan aspektusai, amelyek „nagy fejfájást okoznak a párhuzamos ismétlés miatt” – mondta Regev.

Feige, Kindler és O'Donnell arra összpontosított, hogy megmutassák, hogy a párhuzamos ismétlés a fejfájás ellenére is működhet. „Ezt nagyon bonyolult elemezni kell” – mondta Dana Moshkovitz, az austini Texasi Egyetem elméleti informatikusa. „De ez ijesztően közelinek tűnt. Úgy tűnt, hogy a párhuzamos ismétlés [segít] létrehozni ezt a kapcsolatot a maximális vágástól az egyedi játékokig.”

Bemelegítésként a kutatók megpróbálták megérteni a párhuzamos ismétlést egy egyszerű maximális vágás esetében, amit Moshkovitz „a legostobább max vágásnak” nevezett. Tekintsünk páratlan számú csúcsot, amelyeket élek kötnek össze, hogy kört, vagy „páratlan ciklust” alkossanak. Minden csúcsot két szín valamelyikével szeretne felcímkézni, hogy egyetlen szomszédos csúcspár se legyen azonos színű. Ebben az esetben ez lehetetlen: az egyik él mindig azonos színű csúcsokat köt össze. Törölnie kell ezt az élt, „megtörve” a páratlan ciklust, hogy a gráf megfeleljen a probléma kényszerének. Végső soron minimalizálni szeretné a grafikon megfelelő színezéséhez törölni kívánt élek teljes hányadát.

A párhuzamos ismétlés lehetővé teszi a probléma nagydimenziós változatának mérlegelését – olyat, amelyben meg kell szakítania az összes megjelenő páratlan ciklust. Feige-nek, Kindlernek és O'Donnellnek meg kellett mutatnia, hogy a dimenziók száma nagyon megnőtt, ezért az élek nagyon nagy részét kell törölnie, hogy megtörje az összes páratlan ciklust. Ha ez igaz, az azt jelentené, hogy a párhuzamos ismétlés hatékonyan felerősítheti ennek a „hülye max-vágás” problémának a keménységét.

Ekkor a csapat felfedezett egy furcsa egybeesést: volt egy geometriai módszer annak értelmezésére, hogy a párhuzamos ismétlés úgy működik-e, ahogyan azt remélték. A titok a kocka alakú habok felületében rejlett.

A citromtól a limonádéig

A habok nyelvén átírt problémájuk abból fakadt, hogy bebizonyították, hogy gömbkockák nem létezhetnek – lehetetlen, hogy a nagy dimenziós teret az egész rács mentén olyan cellákra osztják fel, amelyek felülete sokkal kisebb, mint a kocka felülete. (A nagyobb felület megfelel annak, hogy több „rossz” élt kell törölni a páratlan ciklusú gráfból, amint azt az informatikusok remélték mutatni.)

– Úgy gondoltuk, hogy micsoda furcsa geometriai probléma, de ez valószínűleg igaz, nem? – mondta O'Donnell. – Valóban erre volt szükségünk, hogy az igazi válasz legyen. De ő, Feige és Kindler nem tudta bizonyítani. Így 2007-ben ők közzétett egy papírt felvázolják, hogyan tervezték ezt a problémát felhasználni az UGC megtámadására.

Nemsokára reményeik szertefoszlottak.

Ran Raz, a Princeton elméleti informatikusa, aki már több jelentős eredményt is bizonyított a párhuzamos ismétléssel kapcsolatban, felkeltette az érdeklődését cikkük. Úgy döntött, hogy elemzi a párhuzamos ismétlődést a páratlan ciklus problémájára, részben a geometriával való kapcsolat miatt, amelyet Feige, Kindler és O'Donnell fedezett fel.

Raz nem a habproblémával kezdte, hanem élesen támadta a kérdés számítástechnikai változatát. Megmutatta, hogy sokkal kevesebb él törlésével megúszhatja a gráf összes páratlan ciklusát. Más szóval, a párhuzamos ismétlés nem tudja kellőképpen felerősíteni ennek a max-vágási problémának a keménységét. „Azok a paraméterek, amelyeket a párhuzamos ismétlésből kapunk, pontosan nem érik el ezt” – mondta Moshkovitz.

"Az a tervünk, hogy párhuzamos ismétlést használjunk az egyedi játékok keménységének bemutatására, még a legegyszerűbb esetben sem működött" - mondta O'Donnell. – Ez megtörte az egész tervet.

Bár kiábrándító, Raz eredménye a gömbkockák létezésére is utalt: csempézésre alkalmas formák n-dimenziós tér, amelynek felülete a négyzetgyökével arányosan méretezett n. „Úgy voltunk, hogy csináljunk citromból limonádét, és vegyük ezt a kiábrándító technikai eredményt a párhuzamos ismétlésekről és a diszkrét grafikonokról, és alakítsuk át szép, érdekes geometriai eredménnyel” – mondta O'Donnell.

Ő és Kindler, együttműködve az informatikusokkal Anup Rao és a Avi Wigderson, pórul járt Raz bizonyítékán, amíg el nem tanulták elég jól a technikákat ahhoz, hogy lefordítsák a habproblémára. 2008-ban ezt megmutatták gömb alakú kockák valóban lehetségesek.

„Jó módja annak, hogy megindokolja a problémát” – mondta Mark Braverman Princetonból. "Ez gyönyörű."

És kérdéseket vetett fel a történet geometriai oldalán. Mivel Raz párhuzamos ismétlési munkáit használták fel a burkolólap alakjának megalkotásához, Kindler, O'Donnell, Rao és Wigderson valami csúnya és Frankenstein-szerűséget készítettek. A csempe rendetlen volt és tele volt bemélyedésekkel. Matematikai értelemben nem volt konvex. Míg ez megfelelt a céljuknak, a gömbkockából hiányoztak a matematikusok által kedvelt tulajdonságok – olyan tulajdonságok, amelyek konkrétabbá, könnyebben meghatározhatóvá és tanulmányozhatóbbá teszik az alakzatot, és alkalmasabbak a potenciális alkalmazásokra.

„Van valami nagyon nem kielégítő az építésükben” – mondta Regev. „Úgy néz ki, mint egy amőba. Nem úgy néz ki, mint amire számítana, egy szép csempézett test.”

Ez az, amit ő és Naor elindultak megtalálni.

Kiszakadás a ketrecből

Naor és Regev kezdettől fogva rájöttek, hogy a nulláról kell kezdeniük. „Részben azért, mert a domború testek annyira korlátozóak, a korábbi technikák egyikének sem volt esélye a működésre” – mondta. Dor Minzer, a Massachusetts Institute of Technology elméleti informatikusa.

Valójában teljesen valószínű volt, hogy a konvexitás túlságosan korlátozó lenne – hogy konvex gömb alakú kocka egyszerűen nem létezik.

De a múlt hónapban Naor és Regev bebizonyította, hogy tudsz particionálni n-dimenziós tér egész koordináták mentén konvex alakzattal, amelynek felülete nagyon közel van a gömb felületéhez. És ezt teljesen geometrikusan tették – visszaadva a problémát a matematikai gyökerekhez.

Először egy jelentős akadályt kellett megkerülniük. A kocka alakú hab probléma megköveteli, hogy minden csempe egész koordinátákra legyen középre állítva. De az egész rácsban nagyon kis távolságok vannak egyes pontok között – és ezek a rövid távolságok gondot okoznak.

Tekintsünk egy pontot a kétdimenziós rácsban. 1 egységnyire van a legközelebbi pontjaitól vízszintes és függőleges irányban. Átlós irányban azonban a legközelebbi pont $latex sqrt{2}$ egységnyire van – ez az eltérés, amely nagyobb helyeken tovább nő. Ban,-ben n-dimenziós egészrács, a legközelebbi pontok még mindig 1 egységnyire vannak, de ezek az „átlós” pontok most $latex sqrt{n}$ egységnyire vannak. Mondjuk 10,000 100 dimenzióban ez azt jelenti, hogy bármely ponthoz legközelebbi „átlós” szomszédja 10,000 egységnyire van, annak ellenére, hogy van 1 XNUMX másik pont (mindegyik irányban egy), amelyek csak XNUMX egységnyire vannak.

Más rácsokban ez a kétféle távolság arányosan növekszik egymással. A matematikusok évtizedek óta tudják, hogyan lehet ilyen rácsokat minimális felületű konvex formákkal burkolni.

De az egész rácsban a legrövidebb távolságok mindig 1-nél maradnak. Ez akadályozza az optimális felületű, szép megjelenésű csempét. – Valahogy ebbe a ketrecbe zártak – mondta Regev. – Nagyon szorossá tesznek körülötted mindent.

Naor és Regev tehát inkább egy szeletet vett a teljességből n-dimenziós tér. Óvatosan választották ki ezt az alteret, hogy továbbra is gazdag legyen egész pontokban, de egyik pont se legyen túl közel egymáshoz.

Más szóval, az altér, amelyhez végül jutottak, pontosan olyan típusú volt, amelyet a matematikusok már tudtak az optimális csempézéshez.

De ez csak a munka fele volt. Naornak és Regevnek az egész teret fel kellett osztania, nem csak egy szeletét. Ahhoz, hogy egy n-dimenziós gömbkocka, meg kellett szorozniuk a hatékony lapkát a maradék térből származó lapkával (hasonlóan ahhoz, hogy egy kétdimenziós négyzetet egy egydimenziós vonalszakasszal szorozzon meg, hogy háromdimenziós kockát kapjon). Ezzel visszaemelné az építményt az eredeti térbe, de növelné a felületét is.

A párnak meg kellett mutatnia, hogy a megmaradt helyből származó csempe, amely nem volt olyan optimális, nem növelte túl sokat a felületet. Miután ezt megtették, az építkezés befejeződött. (Végső alakjuk felülete valamivel nagyobb lett, mint a nem domború gömbkockáé, de úgy vélik, hogy lehet találni egy olyan konvex lapkát, amely ugyanolyan hatékony, mint a nem konvex megfelelője.)

„A bizonyításuk teljesen más”, mint a gömbkockákkal kapcsolatos korábbi munkák – mondta a matematikus Noga Alon. – És utólag visszagondolva, ez talán természetesebb bizonyíték. Valakinek talán ezzel kellett volna kezdenie.”

„Ha a dolgokat másként csinálják – tette hozzá Raz –, néha érdekes további következményekkel is találkozhatunk.”

Fellángolt a remény

Még nem világos, hogy mik lehetnek ezek a következmények – bár a munka az egész rácsok kriptográfiában és más alkalmazásokban való lehetséges felhasználását érinti. Tekintettel arra, hogy ez a probléma mennyire kapcsolódik más területekhez, „valószínűleg más dolgokhoz vezet” – mondta Alon.

Jelenleg az informatikusok nem látják a módját a konvex eredmény értelmezésének a párhuzamos ismétlés és az UGC nyelvén. De nem adták fel teljesen az eredeti tervet, hogy a habproblémát használják fel a sejtés bizonyítására. "Különféleképpen próbálhatja meg felszámolni azokat a nyilvánvaló akadályokat, amelyekkel találkoztunk" - mondta Kindler.

Braverman és Minzer egy ilyen módszert próbáltak ki, amikor ők újranézett habok 2020-ban. Ahelyett, hogy megkövetelték volna, hogy a burkolólap domború legyen, azt kérték, hogy engedelmeskedjen bizonyos szimmetriáknak, hogy ugyanúgy nézzen ki, akárhogyan is fordítja a koordinátáit. (2D-ben egy négyzet működne, de egy téglalap nem; az eddig leírt nagydimenziós gömbkockák sem.) Ezen új megkötés mellett a pár megmutatta, amit Kindler és mások 15 évvel korábban reméltek: hogy a kocka felületénél mégsem lehet sokkal jobbat csinálni.

Ez egy másfajta párhuzamos ismétlésnek felelt meg – olyannak, amely a lehető legegyszerűbb maximális vágást olyan keménysé tenné, amennyire szükséges. Noha az eredmény némi reményt ad ehhez a kutatási irányhoz, nem világos, hogy a párhuzamos ismétlésnek ez a változata minden max-cut probléma esetén működik-e. – Ez nem jelenti azt, hogy végzett – mondta Braverman. – Ez csak azt jelenti, hogy újra az üzletben van.

„Sok potenciál rejlik a geometriában” – mondta Minzer. "Csak azért, mert nem értjük eléggé."