Number 15 kirjeldab lõpmatu võrgu salajast piiri

Tšiili ülikooli bakalaureuseõppena Bernardo Subercaseaux suhtus arvutite kasutamisesse matemaatika tegemiseks hämaralt. See tundus olevat tõelise intellektuaalse avastuse vastane.

"Seal on teatud instinkt või soole reaktsioon arvutite kasutamise vastu oma probleemide lahendamiseks, nagu see on vastuolus fantastilise argumendi ideaalse ilu või elegantsiga," ütles ta.

Kuid siis aastal 2020 armus Subercaseaux ja nagu sageli juhtub, muutusid tema prioriteedid. Tema kinnisidee objektiks oli küsimus, mida ta nägi internetifoorumis. Enamik probleeme ta skaneeris ja unustas, kuid see jäi talle silma. Ta pühkis paremale.

"Esimese asjana panin postituse Facebooki grupis meeldivaks, lootes saada hiljem teate, kui keegi teine ​​lahenduse postitab," ütles ta.

Küsimus oli lõpmatu ruudustiku täitmise kohta numbritega. Nagu selgus, polnud see probleem, mida lõokes lahendab. Selleks pidi Subercaseaux Tšiilist lahkuma, et lõpetada Carnegie Melloni ülikooli aspirantuur.

Seal oli tal augustis 2021 juhuslik kokkupuude Marijn Heule, arvutiteadlane, kes kasutab raskete matemaatikaküsimuste lahendamiseks tohutut arvutusvõimsust. Subercaseaux küsis Heulelt, kas ta soovib probleemi proovida, käivitades koostöö, mis kulmineerus tänavu jaanuaris. tõestus mille saab kokku võtta ühe arvuga: 15.

Igal võimalikul viisil

Aastal 2002, Wayne Goddard Clemsoni ülikoolist ja mõned sarnaselt mõtlevad matemaatikud heitsid probleeme kombinatoorika vallas, püüdes teatud piiranguid arvestades leida uusi pöördeid valdkonna põhiküsimustes kaartide värvimise kohta.

Lõpuks jõudsid nad probleemini, mis algab ruudustikust, nagu millimeetripaberileht, mis kestab igavesti. Eesmärk on täita see numbritega. On ainult üks piirang: sama numbri iga esinemise vaheline kaugus peab olema suurem kui arv ise. (Kauguse mõõtmiseks liidetakse vertikaalne ja horisontaalne eraldus – mõõdik, mida tuntakse „takso” kaugusena selle järgi, kuidas see meenutab liikumist ruudustikuga linnatänavatel.) Paar 1 ei saa hõivata külgnevaid lahtreid, mille taksokaugus on 1, kuid neid saab paigutada otse diagonaalsetesse lahtritesse, mille vahemaa on 2.

Esialgu soovisid Goddard ja tema kaastöötajad teada, kas on üldse võimalik täita lõpmatut ruudustikku piiratud arvude komplektiga. Kuid selleks ajaks, kui ta ja tema neli kaastöötajat avaldas selle "pakendi värvimise" probleemi ajakirjas Ars Combinatoria 2008. aastal olid nad tõestanud, et seda saab lahendada 22 numbri abil. Samuti teadsid nad, et ainult viie numbriga ei saa seda kuidagi lahendada. See tähendas, et tegelik vastus probleemile – minimaalne vajalik arv numbreid – oli kusagil vahepeal.

Teadlased ei täitnud tegelikult lõpmatut võrku. Nad ei pidanudki. Selle asemel piisab, kui võtta ruudustikust väike alamhulk – näiteks 10 x 10 ruut – täita see numbritega, seejärel näidata, et täidetud alamhulga koopiaid saab paigutada üksteise kõrvale, nii nagu kataksid põrand plaatide koopiatega.

Kui Subercaseaux probleemist esimest korda teada sai, hakkas ta pliiatsi ja paberi abil plaate otsima. Ta visandas arvude ruudustikud, kriipsutas need läbi ja proovis uuesti. Ta tüdines sellest lähenemisest peagi ja ta palus sõbral kujundada veebipõhine tööriist, mis meenutaks mängu Minesweeper ja võimaldaks tal kombinatsioone kiiremini katsetada. Pärast veel paarinädalast tööd oli ta veendunud, et kaheksa numbriga ruudustikku ei saa kuidagi kokku panna, kuid ta ei saanud sellest kaugemale – plaatidel oli lihtsalt liiga palju võimalikke kujundeid ja liiga palju. erinevaid viise, kuidas neid numbritega täita.

Probleem, nagu hiljem selgus, on see, et on palju keerulisem näidata, et ruudustikku ei saa teatud arvude komplekt katta, kui näidata, et see suudab. "See ei näita lihtsalt, et üks viis ei tööta, see näitab, et kõik võimalikud viisid ei tööta," ütles Goddard.

Pärast seda, kui Subercaseaux CMU-s alustas ja veenis Heule temaga koostööd tegema, leidsid nad kiiresti võimaluse katta ruudustik 15 numbriga. Samuti suutsid nad välistada võimaluse probleemi lahendada vaid 12 numbriga. Kuid nende triumfitunne oli lühiajaline, sest nad mõistsid, et nad olid lihtsalt reprodutseerinud tulemusi, mis olid olnud juba pikka aega: juba 2017. aastal teadsid teadlased, et vastus ei olnud väiksem kui 13 ega suurem kui 15 .

Esimese kursuse üliõpilase jaoks, kes sundis staažikat professorit oma lemmikloomaprobleemiga tegelema, oli see murettekitav avastus. "Ma olin kohkunud. Ma olin põhimõtteliselt mitu kuud töötanud probleemi kallal, ilma et oleksin sellest aru saanud, ja mis veelgi hullem, olin teinud Marijni raiskab sellele oma aega!” Subercaseaux kirjutas blogipostituses, mis võtab kokku nende tööd.

Heule aga pidas varasemate tulemuste avastamist kosutavaks. See näitas, et teised teadlased pidasid probleemi piisavalt oluliseks, et selle kallal töötada, ja kinnitas tema jaoks, et ainus tulemus, mida tasub saavutada, on probleemi täielik lahendamine.

"Kui saime aru, et probleemiga oli tööd tehtud 20 aastat, muutis see pilti täielikult," ütles ta.

Vulgarite vältimine

Aastate jooksul oli Heule teinud karjääri, otsides tõhusaid viise tohutute võimalike kombinatsioonide hulgast otsimiseks. Tema lähenemisviisi nimetatakse SAT-lahenduseks - lühend sõnadest "rahuldavus". See hõlmab pika valemi, mida nimetatakse Boole'i ​​valemiks, koostamist, millel võib olla kaks võimalikku tulemust: 0 või 1. Kui tulemus on 1, on valem tõene ja probleem on täidetud.

Pakkimise värvimisprobleemi puhul võib valemis iga muutuja näidata, kas antud lahter on hõivatud teatud arvuga. Arvuti otsib valemi täitmiseks viise muutujate määramiseks. Kui arvuti saab sellega hakkama, siis teate, et teie määratud tingimustel on võimalik ruudustikku pakkida.

Kahjuks võib pakkimise värvimisprobleemi otsene kodeerimine Boole'i ​​valemina ulatuda paljude miljonite terminiteni – arvuti või isegi arvutipark võib igavesti katsetada kõiki selles muutujate määramise erinevaid viise.

"Selle toore jõuga proovimine võtaks aega, kuni universum lõpeb, kui teete seda naiivselt," ütles Goddard. "Nii et teil on vaja lahedaid lihtsustusi, et viia see millekski, mis on isegi võimalik."

Veelgi enam, iga kord, kui lisate pakendi värvimisprobleemile numbri, muutub see võimalike kombinatsioonide paljunemise tõttu umbes 100 korda raskemaks. See tähendab, et kui paralleelselt töötav arvutite pank suudaks ühe arvutuspäeva jooksul välistada 12, vajaksid nad 100 välistamiseks 13 päeva arvutusaega.

Heule ja Subercaseaux pidasid toore jõuga arvutusmeetodi suurendamist teatud mõttes vulgaarseks. "Meil oli mitu paljutõotavat ideed, nii et võtsime mõtteviisi: "Proovime oma lähenemisviisi optimeerida, kuni suudame selle probleemi lahendada klastris vähem kui 48-tunnise arvutustööga," ütles Subercaseaux.

Selleks pidid nad leidma viisid, kuidas piirata arvutusklastri proovitavate kombinatsioonide arvu.

"[Nad] ei taha seda mitte ainult lahendada, vaid ka muljetavaldavalt," ütles Aleksander Soifer Colorado ülikoolist Colorado Springsis.

Heule ja Subercaseaux tõdesid, et paljud kombinatsioonid on sisuliselt samad. Kui proovite täita rombikujulist paani kaheksa erineva numbriga, pole vahet, kas esimene number, mille panite, on üks üleval ja üks keskruudust paremal või üks alla ja üks vasakule keskväljakul. Need kaks paigutust on üksteise suhtes sümmeetrilised ja piiravad teie järgmist käiku täpselt samal viisil, seega pole põhjust neid mõlemaid kontrollida.

Heule ja Subercaseaux lisasid reeglid, mis võimaldasid arvutil käsitleda sümmeetrilisi kombinatsioone samaväärsetena, vähendades kogu otsinguaega kaheksa korda. Nad kasutasid ka tehnikat, mille Heule oli varasemates töödes välja töötanud nimega cube and conquer, mis võimaldas neil katsetada paralleelselt rohkem kombinatsioone. Kui teate, et antud lahter peab sisaldama kas 3, 5 või 7, saate probleemi jagada ja testida kõiki kolme võimalust samaaegselt erinevates arvutikomplektides.

2022. aasta jaanuariks võimaldasid need täiustused Heulel ja Subercaseaux'l välistada 13 vastusena pakendi värvimisprobleemile katses, mis nõudis vähem kui kahepäevast arvutusaega. See jättis neile kaks võimalikku vastust: 14 või 15.

Suur pluss

14 välistamiseks ja probleemi lahendamiseks pidid Heule ja Subercaseaux leidma täiendavaid viise arvutiotsingu kiirendamiseks.

Algselt olid nad kirjutanud Boole'i ​​valemi, mis määras ruudustiku igale üksikule lahtrile muutujad. Kuid 2022. aasta septembris mõistsid nad, et neil pole vaja lahtri kaupa edasi minna. Selle asemel avastasid nad, et tõhusam on vaadelda väikeseid piirkondi, mis koosnevad viiest plussmärgi kujulisest rakust.

Nad kirjutasid oma Boole'i ​​valemi ümber nii, et mitmed muutujad esindasid selliseid küsimusi nagu: kas selles pluss-kujulises piirkonnas on kuskil 7? Arvuti ei pidanud täpselt tuvastama, kus piirkonnas 7 võiks olla. See pidi lihtsalt kindlaks tegema, kas see oli seal või mitte - küsimus, millele vastamiseks on vaja oluliselt vähem arvutusressursse.

"Muutujate olemasolu, mis räägivad konkreetsete asukohtade asemel ainult plussidest, osutusid palju paremaks kui neist konkreetsetes lahtrites rääkimine," ütles Heule.

Tänu plussotsingu tõhususele välistasid Heule ja Subercaseaux 14. aasta novembris arvutikatses 2022, mille käivitamine võttis vähem aega kui see, mida nad kasutasid 13 välistamiseks. Järgmised neli kuud kontrollisid nad, et arvuti järeldus oli õige – peaaegu sama palju aega, kui nad olid kulutanud selleks, et arvuti jõudis selle järelduseni.

"Oli rõõmustav mõelda, et see, mille me mingis juhuslikus ajakirjas omamoodi kõrvalküsimusena esitasime, oli pannud inimrühmad kulutama, nagu selgus, kuid oma ajast selle lahendamisele," Goddard. ütles.

Subercaseaux’ jaoks oli see tema teadlaskarjääri esimene tõeline triumf. Ja kuigi see ei pruukinud olla seda tüüpi avastus, mida ta oli idealiseerinud, kui ta esimest korda matemaatika alal töötamist kaalus, leidis ta, et lõpuks on sellel oma intellektuaalne kasu.

"See ei ole vormi mõistmine, kui annate mulle tahvli ja ma võin teile näidata, miks see on 15," ütles ta. "Kuid oleme saanud arusaama sellest, kuidas probleemi piirangud toimivad, kui palju parem on 6 siin või 7 seal. Oleme omandanud palju intuitiivset mõistmist.