Matemaatikot suorittavat tehtävänsä "pallomaisten kuutioiden" rakentamiseksi

Neljännellä vuosisadalla kreikkalainen matemaatikko Pappus Aleksandriasta ylisti mehiläisiä heidän "geometrisestä ennakoinnistaan". Heidän hunajakennänsä kuusikulmainen rakenne vaikutti optimaaliselta tapa jakaa kaksiulotteinen tila soluiksi, joiden pinta-ala ja minimaalinen ympärysmitta – jolloin hyönteiset voivat vähentää tuotantoon tarvittavan vahan määrää ja käyttää vähemmän aikaa ja energiaa oman rakenteensa rakentamiseen. pesä.

Tai niin Pappus ja muut olettivat. Vuosituhansien ajan kukaan ei pystynyt todistamaan, että kuusikulmiot olivat optimaalisia – kunnes lopulta vuonna 1999 matemaatikko Thomas Hales osoitti, ettei mikään muu muoto voisi toimia paremmin. Nykyään matemaatikot eivät vieläkään tiedä, mitkä muodot voivat laatoittaa kolme tai useampia ulottuvuuksia pienimmällä mahdollisella pinta-alalla.

Tällä "vaahto"-ongelmalla on osoittautunut olevan laaja-alaisia ​​sovelluksia - saippuakuplien (tai vaahtojen) käyttäytymistä tutkiville fyysikoille ja kiteiden rakennetta analysoiville kemisteille, matemaatikoille, jotka tutkivat pallojen pakkausjärjestelyjä, ja tilastotieteilijöille, jotka kehittävät tehokkaita tietojenkäsittelytekniikoita. .

2000-luvun puolivälissä vaahtoongelman erityinen muotoilu kiinnitti huomiota myös teoreettisiin tietotekniikan tutkijoihin, jotka huomasivat yllätykseksi, että se liittyy syvästi heidän alansa tärkeään avoimeen ongelmaan. He pystyivät käyttämään tätä yhteyttä löytääkseen uuden korkeaulotteisen muodon, jolla on minimaalinen pinta-ala.

"Rakastan tätä edestakaisin", sanoi Assaf Naor Princetonin yliopistosta. ”Joistakin vanhasta matematiikasta tulee merkityksellistä tietojenkäsittelytieteelle; tietojenkäsittelytiede maksaa takaisin ja ratkaisee kysymyksen matematiikassa. On todella mukavaa, kun näin tapahtuu.”

Mutta tuosta muodosta, vaikkakin optimaalisesta, puuttui jotain tärkeää: geometrinen perusta. Koska sen olemassaolo oli todistettu tietojenkäsittelytieteen tekniikoilla, sen todellinen geometria oli vaikea käsittää. Sitä Naor yhdessä Oded Regev, tietojenkäsittelytieteilijä New Yorkin yliopiston Courant Institutessa, päätti korjata asian viime kuussa verkossa julkaistu todiste.

"Se on erittäin mukava lopetus tarinalle", Regev sanoi.

Kuutiomaiset vaahdot

Matemaatikot ovat harkinneet muita versioita vaahtoongelmasta - mukaan lukien mitä tapahtuu, jos tilan sallitaan vain osioida niin kutsutun kokonaislukuhilan mukaan. Tässä tehtävän versiossa otat tasaisesti sijoitettujen pisteiden neliömäisen matriisin (kukin 1 yksikön päässä toisistaan) ja teet jokaisesta pisteestä muodon keskipisteen. "Kuutiomainen" vaahtoongelma kysyy, mikä on pienin pinta-ala, kun tilaa laatoitetaan tällä tavalla.

Tutkijat olivat alun perin kiinnostuneita tämän rajoituksen asettamisesta ymmärtääkseen monimuotoisiksi kutsuttujen topologisten tilojen ominaisuuksia. Mutta kysymys sai oman elämänsä, ja siitä tuli merkityksellinen data-analyysissä ja muissa sovelluksissa.

Se on myös geometrisesti mielenkiintoinen, koska se muuttaa mitä "optimaalinen" voi tarkoittaa. Esimerkiksi kahdessa ulottuvuudessa säännölliset kuusikulmiot eivät voi enää laatoittaa tasoa, jos niitä voidaan siirtää vain kokonaislukumäärällä vaaka- ja pystysuunnassa. (Sinun on siirrettävä niitä irrationaalisesti jompaankumpaan suuntaan.)

Neliöt voivat. Mutta onko se parasta mitä voidaan tehdä? Matemaatikkona Jaigyoung Choe löydettiin vuonna 1989, vastaus on ei. Optimaalinen muoto on sen sijaan kuusikulmio, joka on puristettu yhteen suuntaan ja pidennetty toiseen suuntaan. (Tällaisen kuusikulmion ympärysmitta on noin 3.86, kun sen pinta-ala on 1, mikä ylittää neliön kehän 4.)

Nämä erot saattavat tuntua vähäpätöisiltä, ​​mutta ne kasvavat paljon korkeammissa ulottuvuuksissa.

Tietyn tilavuuden kaikista muodoista pinta-alan minimoinut pallo on. Kuten n, mittojen lukumäärä, kasvaa, pallon pinta-ala kasvaa suhteessa neliöjuureen n.

Mutta pallot eivät voi laatoittaa tilaa jättämättä aukkoja. Toisaalta an n-ulotteinen kuutio, jonka tilavuus on 1 tölkki. Pääasia on, että sen pinta-ala on 2nkasvaa suoraan suhteessa sen kokoon. 10,000 1-ulotteisen kuution, jonka tilavuus on 20,000, pinta-ala on 400 10,000 - paljon suurempi kuin XNUMX, likimääräinen XNUMX XNUMX-ulotteisen pallon pinta-ala.

Ja niin tutkijat ihmettelivät, voisivatko he löytää "pallomaisen kuution" - muodon, joka laatoittaa n-ulotteinen avaruus, kuten kuutio, mutta jonka pinta-ala kasvaa hitaasti, kuten pallon.

Se näytti epätodennäköiseltä. "Jos haluat kuplan täyttävän tarkasti tilan ja olevan tämän kuutiomaisen ruudukon keskipisteenä, on vaikea ajatella, mitä käyttäisit kuutiomaista kuplaa lukuun ottamatta", sanoi Ryan O'Donnell, teoreettinen tietojenkäsittelytieteilijä Carnegie Mellonin yliopistossa. "Näyttää todella, että kuution pitäisi olla paras."

Tiedämme nyt, että se ei ole.

Vaikeiden ongelmien kovuus

Kuutiovaahto-ongelma jäi vuosikymmeniä suhteellisen tutkimatta suuremmissa mitoissa. Ensimmäiset tutkijat, jotka edistyivät siinä, eivät tulleet geometrian alueelta vaan teoreettisesta tietojenkäsittelytieteestä. He törmäsivät siihen sattumalta etsiessään tapaa todistaa alansa keskeisen lausunnon, joka tunnetaan nimellä ainutlaatuisia pelejä. "Ainutlaatuinen peliarvaus", Regev sanoi, "on mielestäni tällä hetkellä suurin avoin kysymys teoreettisessa tietojenkäsittelytieteessä."

Ehdotus vuonna 2002 Subhash Khot, tuolloin jatko-opiskelija, olettamus olettaa, että jos tiettyä ongelmaa - joka liittyy värien määrittämiseen verkon solmuille - ei voida ratkaista tarkasti, niin likimääräisen ratkaisun löytäminen on erittäin vaikeaa. Jos olettamus pitää paikkansa, tutkijat voisivat ymmärtää suuren valikoiman muita laskennallisia tehtäviä yhdellä iskulla.

Tietojenkäsittelytieteilijät luokittelevat tehtävät usein sen perusteella, voidaanko ne ratkaista tehokkaalla algoritmilla vai ovatko ne sen sijaan "NP-kovia" (eli niitä ei voida ratkaista tehokkaasti ongelman koon kasvaessa, kunhan yleisesti uskotaan mutta todistamaton olettamus laskennallisesta monimutkaisuudesta on totta). Esimerkiksi matkustavan myyjän ongelma, joka kysyy lyhimmän polun jokaiseen verkoston kaupunkiin käymiseen vain kerran, on NP-kova. Samoin sen määrittäminen, voidaanko graafi – kokoelma reunojen yhdistämiä pisteitä – merkitä enintään kolmella värillä siten, että kahdella yhdistetyllä pisteellä on eri värit.

Osoittautuu, että moniin näistä tehtävistä on NP-vaikea löytää edes likimääräistä ratkaisua. Oletetaan, että haluat merkitä graafin kärjet eri väreillä tavalla, joka täyttää rajoitusluettelon. Jos on NP-vaikea täyttää kaikkia noita rajoituksia, entä yrittää täyttää vain 90 % niistä, tai 75 % tai 50 %? Jonkin kynnyksen alapuolella saattaa olla mahdollista keksiä tehokas algoritmi, mutta sen yläpuolella ongelmasta tulee NP-kova.

Tietojenkäsittelytieteilijät ovat vuosikymmenten ajan työskennelleet kynnysten naulitsemiseksi erilaisille kiinnostaville optimointiongelmille. Mutta jotkut kysymykset välttelevät tällaista kuvausta. Vaikka algoritmi saattaa taata 80 % parhaasta ratkaisusta, voi olla NP-vaikea saavuttaa 95 % parhaasta ratkaisusta, mikä jättää ratkaisematta kysymyksen siitä, missä tarkalleen 80-95 %:lla ongelma kaatuu NP-kovalle alueelle.

Ainutlaatuinen pelien arvelu eli UGC tarjoaa tavan löytää vastaus välittömästi. Se antaa lausunnon, joka vaikuttaa aluksi rajallisemmalta: että on NP-vaikea erottaa graafin, jolla voit täyttää melkein kaikki tietyt värirajoitukset (esimerkiksi yli 99 %), ja graafin välillä. joita voit täyttää tuskin yhtään (esimerkiksi alle 1 %).

Mutta pian sen jälkeen, kun UGC:tä ehdotettiin vuonna 2002, tutkijat osoittivat, että jos olettamus on totta, voit helposti laskea kovuuskynnyksen mille tahansa rajoitteen tyytyväisyysongelmalle. (Tämä johtuu siitä, että UGC viittaa myös siihen, että tunnettu algoritmi saavuttaa parhaan mahdollisen likiarvon kaikille näille ongelmille.) "Se oli juuri kaikkien näiden optimointiongelmien tukikohta", O'Donnell sanoi.

Niinpä teoreettiset tietojenkäsittelytieteilijät ryhtyivät todistamaan UGC:tä – tehtävää, joka lopulta johti osan heistä löytämään pallomaisia ​​kuutioita.

Vaikeiden ongelmien tekeminen vaikeammaksi

Vuonna 2005 O'Donnell työskenteli Microsoft Researchissä. Hän ja kaksi kollegaa - Uriel Feige, nyt Weizmann Institute of Sciencessa ja Guy Kindler, nyt Jerusalemin heprealaisessa yliopistossa – liittoutui torjumaan UGC:tä.

Heillä oli epämääräinen käsitys siitä, kuinka he halusivat edetä. He aloittaisivat kysymyksellä kaavioista - kysymyksestä, joka on hyvin samanlainen kuin UGC. Ns. maksimileikkaus ("max-cut") -ongelma kysyy, kun graafi annetaan, kuinka sen kärjet jaetaan kahdeksi joukoksi (tai väreiksi) niin, että niitä yhdistävien reunojen määrä on mahdollisimman suuri. (Voit ajatella max cut -kysymystä siitä, mikä on paras tapa värittää graafi kahdella värillä, jotta mahdollisimman harvat reunat yhdistävät samanvärisiä pisteitä.)

Jos UGC on tosi, se merkitsisi, että tietyllä satunnaisella graafilla tehokas approksimaatioalgoritmi voi päästä vain noin 87 %:n etäisyydelle graafin todellisesta maksimileikkauksesta. Paremman tekeminen olisi NP-vaikeaa.

Feige, Kindler ja O'Donnell halusivat sen sijaan mennä päinvastaiseen suuntaan: he toivoivat osoittavansa, että maksimileikkausta on vaikea arvioida, ja sitten käyttää sitä todistamaan UGC. Heidän suunnitelmansa perustui rinnakkaistoistoksi kutsutun tekniikan vahvuuteen – älykkääseen strategiaan, joka vaikeuttaa vaikeita ongelmia.

Oletetaan, että tiedät, että on NP-vaikea erottaa ongelma, jonka voit ratkaista, ja ongelman, jonka voit enimmäkseen ratkaista. Rinnakkaistoiston avulla voit rakentaa sen päälle ja näyttää paljon vahvemman kovuustuloksen: että on myös NP-vaikea erottaa ongelma, jonka voit ratkaista, ja ongelman, jota voit tuskin ratkaista. "Tämä epäintuitiivinen, syvä ilmiö … on monien tietojenkäsittelytieteen sisimmässä nykyään", Naor sanoi.

Mutta siinä on saalis. Rinnakkaistoisto ei aina lisää ongelman kovuutta niin paljon kuin tietojenkäsittelytieteilijät haluavat sen. Erityisesti max-cut-ongelmassa on näkökohtia, jotka "luovat suuren päänsäryn rinnakkaiselle toistolle", Regev sanoi.

Feige, Kindler ja O'Donnell keskittyivät osoittamaan, että rinnakkainen toisto voi toimia päänsäryistä huolimatta. "Tämä on todella monimutkainen analysoitava asia", sanoi Dana Moshkovitz, teoreettinen tietojenkäsittelytieteilijä Texasin yliopistossa Austinissa. "Mutta tämä vaikutti kiehtovan läheltä. Rinnakkaistoisto näytti siltä, ​​että se [auttaa] tämän yhteyden maksimileikkauksesta ainutlaatuisiin peleihin."

Alkulämmittelynä tutkijat yrittivät ymmärtää rinnakkaista toistoa yksinkertaisessa maksimileikkaustapauksessa, jota Moshkovitz kutsui "tyhmimmäksi maksimileikkaukseksi". Harkitse paritonta määrää kärkejä, jotka on yhdistetty reunoilla ympyrän tai "parittoman syklin" muodostamiseksi. Haluat merkitä jokaisen kärjen yhdellä kahdesta väristä, jotta millään vierekkäisten kärkien parilla ei ole samaa väriä. Tässä tapauksessa se on mahdotonta: Yksi reuna yhdistää aina samanväriset kärjet. Sinun on poistettava tämä reuna ja "katkaistava" pariton sykli saadaksesi graafisi täyttämään ongelman rajoitteen. Loppujen lopuksi haluat minimoida niiden reunojen kokonaisosuuden, jotka sinun on poistettava, jotta voit värittää kuvaajan oikein.

Rinnakkaistoiston avulla voit harkita tämän ongelman korkean ulottuvuuden versiota - sellaisen, jossa sinun on katkaistava kaikki esiin tulevat parittomat syklit. Feigen, Kindlerin ja O'Donnellin oli osoitettava, että kun mittojen lukumäärä kasvaa erittäin suureksi, sinun on poistettava erittäin suuri osa reunoista, jotta kaikki parittomat syklit katkeaa. Jos tämä olisi totta, se tarkoittaisi, että rinnakkainen toisto voisi tehokkaasti vahvistaa tämän "tyhmän maksimileikkaus" -ongelman kovuutta.

Silloin ryhmä havaitsi omituisen sattuman: oli geometrinen tapa tulkita, toimisiko rinnakkainen toisto heidän toivomallaan tavalla. Salaisuus piilee kuutiomaisten vaahtojen pinta-alassa.

Sitruunasta limonadiin

Heidän ongelmansa, joka kirjoitettiin uudelleen vaahtojen kielellä, kiteytyi osoittamaan, että pallomaisia ​​kuutioita ei voi olla olemassa - että on mahdotonta jakaa korkeaulotteista tilaa kokonaislukuhilaa pitkin soluiksi, joiden pinta-ala on paljon pienempi kuin kuution pinta-ala. (Suurempi pinta-ala vastaa tarvetta poistaa enemmän "huonoja" reunoja parittomien syklien kaaviosta, kuten tietojenkäsittelytieteilijät toivoivat osoittavan.)

"Olimme kuin, oi, mikä outo geometriaongelma, mutta se on luultavasti totta, eikö?" O'Donnell sanoi. "Tarvitsimme sen todella ollaksemme oikea vastaus." Mutta hän, Feige ja Kindler eivät pystyneet todistamaan sitä. Joten vuonna 2007 he julkaisi paperin hahmotellaan kuinka he aikoivat käyttää tätä ongelmaa hyökätäkseen UGC:tä vastaan.

Pian heidän toiveensa petettiin.

Ran Raz, Princetonin teoreettinen tietojenkäsittelytieteilijä, joka oli jo osoittanut useita merkittäviä tuloksia rinnakkaisesta toistosta, kiinnosti heidän artikkelistaan. Hän päätti analysoida rinnakkaista toistoa parittoman syklin ongelman osalta, osittain siksi, että Feige, Kindler ja O'Donnell olivat löytäneet yhteyden geometriaan.

Raz ei aloittanut vaahto-ongelmasta, vaan hyökkäsi suoraan kysymyksen tietojenkäsittelytieteen versiota vastaan. Hän osoitti, että voit päästä eroon poistamalla paljon vähemmän reunoja rikkoaksesi kaikki kaavion parittomat jaksot. Toisin sanoen rinnakkainen toisto ei voi riittävästi vahvistaa tämän max-cut-ongelman kovuutta. "Parametrit, jotka saadaan täsmälleen rinnakkaisesta toistosta, jäävät täsmälleen alle tämän", Moshkovitz sanoi.

"Suunnitelmamme käyttää rinnakkaista toistoa ainutlaatuisten pelien kovuuden osoittamiseen ei toiminut edes yksinkertaisimmassa tapauksessa", O'Donnell sanoi. "Tämä rikkoi koko suunnitelman."

Vaikka Razin tulos olikin pettymys, se vihjasi myös pallomaisten kuutioiden olemassaoloon: muotoihin, jotka pystyvät laatoittamaan n-ulotteinen avaruus, jonka pinta-ala on skaalattu suhteessa neliöjuureen n. "Ajattelimme, että tehdään limonadi sitruunoista ja tehdään tämä pettymys tekninen tulos rinnakkaisista toistoista ja diskreetistä kaaviosta ja tehdään siitä siisti, mielenkiintoinen geometria", O'Donnell sanoi.

Hän ja Kindler yhteistyössä tietotekniikan tutkijoiden kanssa Anup Rao ja Avi Wigderson, pohdiskeli Razin todisteita, kunnes he olivat oppineet sen tekniikat riittävän hyvin kääntääkseen ne vaahtoongelmaksi. Vuonna 2008 he osoittivat sen pallomaiset kuutiot ovat todellakin mahdollisia.

"Se on hyvä tapa perustella ongelmaa", sanoi Mark Braverman Princetonista. "Se on kaunis."

Ja se herätti kysymyksiä tarinan geometriasta. Koska he olivat käyttäneet Razin työtä rinnakkaisessa toistossa rakentaessaan laatoitusmuotonsa, Kindler, O'Donnell, Rao ja Wigderson päätyivät johonkin rumaan ja Frankensteinin kaltaiseen. Laatta oli sotkuinen ja täynnä painaumia. Matemaattisesti se ei ollut kupera. Vaikka tämä toimi heidän tarkoituksiinsa, pallomaisesta kuutiosta puuttui ominaisuuksia, joita matemaatikot suosivat - ominaisuuksia, jotka tekevät muodosta konkreettisemman, helpompi määritellä ja tutkia ja jotka sopivat paremmin mahdollisiin sovelluksiin.

"Heidän rakentamisessa on jotain erittäin epätyydyttävää", Regev sanoi. "Se näyttää amebalta. Se ei näytä siltä, ​​mitä odotat, hieno laatoitettu runko.”

Sitä hän ja Naor lähtivät etsimään.

Vapautua häkistä

Alusta alkaen Naor ja Regev ymmärsivät, että heidän oli aloitettava tyhjästä. "Osittain siksi, että kuperat kappaleet ovat niin rajoittavia, millään aikaisemmista tekniikoista ei ollut mahdollisuutta toimia", sanoi Dor Minzer, teoreettinen tietotekniikan tutkija Massachusetts Institute of Technologysta.

Itse asiassa oli täysin todennäköistä, että kupera olisi liian rajoittava - kuperaa pallomaista kuutiota ei yksinkertaisesti ole olemassa.

Mutta viime kuussa Naor ja Regev osoittivat, että osaat jakaa n-ulotteinen avaruus kokonaislukukoordinaatteja pitkin kuperalla muodolla, jonka pinta-ala on melko lähellä pallon pinta-alaa. Ja he tekivät sen täysin geometrisesti - palauttaen ongelman matemaattisille juurilleen.

Heidän täytyi ensin kiertää suuri este. Kuutiovaahto-ongelma edellyttää, että jokainen laatta on keskitetty kokonaislukukoordinaatteihin. Mutta kokonaislukuhilassa joidenkin pisteiden välillä on hyvin lyhyitä etäisyyksiä - ja nuo lyhyet etäisyydet aiheuttavat ongelmia.

Tarkastellaan pistettä kaksiulotteisessa ruudukossa. Se sijaitsee 1 yksikön päässä lähimmästä pisteestään vaaka- ja pystysuunnassa. Mutta diagonaalisuunnassa lähin piste on $latex sqrt{2}$ yksikön päässä – ero, joka pahenee suuremmissa tiloissa. Vuonna n-ulotteinen kokonaislukuhila, lähimmät pisteet ovat edelleen 1 yksikön päässä, mutta nämä "diagonaaliset" pisteet ovat nyt $latex sqrt{n}$ yksikön päässä. Esimerkiksi 10,000 100 ulottuvuudessa tämä tarkoittaa, että minkä tahansa pisteen lähin "diagonaalinen" naapuri on 10,000 yksikön päässä, vaikka on 1 XNUMX muuta pistettä (yksi kumpaankin suuntaan), jotka ovat vain XNUMX yksikön päässä.

Muissa hiloissa nämä kahdenlaiset etäisyydet kasvavat suhteessa toisiinsa. Matemaatikot ovat tienneet vuosikymmeniä, kuinka tällaiset ristikot laatoitetaan kuperilla muotoilla, joiden pinta-ala on minimaalinen.

Mutta kokonaislukuhilassa lyhyimmät etäisyydet ovat aina jumissa 1:ssä. Tämä estää optimaalisen pinta-alaltaan hyvännäköisen laatan rakentamisen. "He laittoivat sinut tähän häkkiin", Regev sanoi. "He tekevät kaikesta erittäin tiukkaa ympärilläsi."

Joten Naor ja Regev pitivät sen sijaan siivua täydestä n-ulotteinen tila. He valitsivat tämän aliavaruuden huolellisesti, jotta se olisi edelleen runsaasti kokonaislukupisteitä, mutta mikään näistä pisteistä ei olisi liian lähellä toisiaan.

Toisin sanoen aliavaruus, johon he päätyivät, oli juuri sitä tyyppiä, jonka matemaatikot osasivat jo laatoittaa optimaalisesti.

Mutta tämä oli vain puolet työstä. Naorin ja Regevin täytyi jakaa koko tila, ei vain osa siitä. Saadaksesi an n-ulotteinen pallomainen kuutio, heidän täytyi kertoa tehokas laatta jäljellä olevasta tilasta olevalla laatalla (samaan tapaan kuin voit kertoa kaksiulotteisen neliön yksiulotteisella viivasegmentillä saadaksesi kolmiulotteisen kuution). Tämä nostaisi niiden rakenteet takaisin alkuperäiseen tilaan, mutta se myös kasvattaisi sen pinta-alaa.

Parin oli osoitettava, että jäljellä olevan tilan laatta, joka ei ollut yhtä optimaalinen, ei lisännyt pinta-alaa liikaa. Kun he tekivät sen, heidän rakentamisensa oli valmis. (Niiden lopullisen muodon pinta-ala oli lopulta hieman suurempi kuin ei-kuperan pallomaisen kuution pinta-ala, mutta he uskovat, että voisi olla mahdollista löytää kupera laatta, joka on yhtä tehokas kuin sen ei-kupera vastine.)

"Heidän todisteensa on täysin erilainen" kuin aikaisemmissa pallomaisissa kuutioissa tehdyissä töissä, sanoi matemaatikko Noga Alon. ”Ja jälkikäteen katsottuna se on ehkä luonnollisempi todiste. Tästä jonkun olisi ehkä pitänyt yrittää aloittaa."

"Kun asiat tehdään toisin", Raz lisäsi, "joskus löydät mielenkiintoisia lisävaikutuksia."

Toivo syttyi uudelleen

Ei ole vielä selvää, mitkä nämä vaikutukset voivat olla - vaikka työ käsittelee kokonaislukuhilan mahdollista käyttöä kryptografiassa ja muissa sovelluksissa. Koska tämä ongelma liittyy muihin aloihin, "se todennäköisesti johtaa muihin asioihin", Alon sanoi.

Tällä hetkellä tietojenkäsittelytieteilijät eivät näe tapaa tulkita kuperaa tulosta rinnakkaisen toiston ja UGC:n kielellä. Mutta he eivät ole täysin luopuneet alkuperäisestä suunnitelmasta käyttää vaahtoongelmaa oletuksen todistamiseen. "On olemassa useita tapoja, joilla voit yrittää kumota havaitsemamme ilmeiset esteet", Kindler sanoi.

Braverman ja Minzer kokeilivat yhtä sellaista tapaa, kun he tarkistettu vaahdot vuonna 2020. Sen sijaan, että vaatisivat laatoituksen muodon olevan kupera, he pyysivät sitä noudattamaan tiettyjä symmetrioita, jotta se näyttää samalta riippumatta siitä, kuinka käännät sen koordinaatteja. (2D:ssä neliö toimisi, mutta suorakulmio ei; eivät myöskään tähän mennessä kuvatut korkean ulottuvuuden pallomaiset kuutiot.) Tämän uuden rajoitteen alaisena pari pystyi näyttämään sen, mitä Kindler ja muut olivat toivoneet 15 vuotta aiemmin: että et voikaan tehdä paljon parempaa kuin kuution pinta-ala.

Tämä vastasi toisenlaista rinnakkaista toistoa – sellaista, joka tekisi yksinkertaisimmasta maksimileikkauksesta niin kovan kuin sen piti. Vaikka tulos tarjoaa jonkin verran toivoa tälle tutkimuslinjalle, ei ole selvää, toimiiko tämä rinnakkaisen toiston versio kaikissa max-cut-ongelmissa. "Se ei tarkoita, että olet valmis", Braverman sanoi. "Se tarkoittaa vain, että olet palannut liiketoimintaan."

"Geometriassa on paljon potentiaalia", Minzer sanoi. "Me emme vain ymmärrä sitä tarpeeksi hyvin."