Arvutiteadlased on peamisele algoritmilisele eesmärgile lähemal | Quanta ajakiri

Kui keegi palub teil kindlaks teha, kas kaks objekti on samad, võib see tunduda triviaalse taotlusena. Enamikul igapäevastel juhtudel piisab täpse otsuse tegemiseks kiirest pilgust.

Kuid arvutiteaduses on see palju rohkem seotud küsimus. Tegelikult on see üks, mis lõikab arvutite võimekuse lahendamata südamesse. Olenevalt sellest, millised on objektid ja kuidas te samasust määratlete, ei tea me ikkagi, kas arvutid suudavad sellele küsimusele kiiresti vastata või on aeglane ja töömahukas lähenemine sisuliselt parim, mida nad suudavad hallata.

Viimase kümnendi jooksul on saavutatud mõned olulised tulemused, mis näitavad, et arvutid suudavad sellest vähemalt natuke paremini hakkama saada. Üks neist viimase aja suurimad tulemused arvutiteaduses oli kiirem algoritm kahe graafiku ühesuguse määramiseks. 2015. aasta töö, autor László Babai Chicago ülikoolist, murdis ühe olulise arvutusliku kiiruse barjääri, kuid jäi teisele alla.

Nüüd paber Xiaorui päike Chicago Illinoisi ülikoolis on esitatud uus, kiirem algoritm seotud küsimusele, mida nimetatakse rühma isomorfismi probleemiks, mille eesmärk on teada, millal kaks matemaatilist objekti, mida nimetatakse rühmadeks, on samad. Töö, postitatud Internetis möödunud märtsis, astub väikese sammu objektide võrdlemise aluseks oleva arvutusliku keerukuse selgitamiseks.

Suni töö rikub teatud rühmade klassi jaoks pikaajalist kiiruspiirangut - seda, mida peetakse rühma isomorfismi probleemi kõige raskemini lahendatavaks juhtumiks. Kui algoritm suudab seda tüüpi rühmi kiiresti võrrelda, on lootus, et see suudab kiiresti võrrelda mis tahes tüüpi rühmi.

"Me ei tea sellist teoreemi, kuid meil on põhjust arvata, et midagi sellist peaks tõsi olema," ütles Josh Grochow Colorado ülikoolist, Boulder.

Võrdluste võrdlemine

Et teha kindlaks, kas kaks asja on täpselt samad, peate esmalt defineerima "sama". Kahte numbrijada võib pidada samaks, kui need sisaldavad samu numbreid või võib-olla peavad neil olema samad numbrid samas järjekorras.

Isomorfism on teatud tüüpi võrdsus, mis tuleb matemaatikas palju ette. Kui kaks objekti on üksteise suhtes isomorfsed, tähendab see ligikaudu, et need sisaldavad samu elemente ja et need elemendid on üksteisega samas suhtes.

Graafikud – servade (joontega) seotud tippude (punktide) kogumid – pakuvad ligipääsetavat visuaalset viisi, kuidas näha, milline isomorfism võib välja näha. Kaks graafi on isomorfsed, kui saate ühe graafi tippe sobitada teise tippudega, nii et tipud, mis on esimeses graafis ühendatud servaga, on ühendatud servaga teises. Isomorfsed graafikud võivad pinnalt erinevad välja näha, kuid neil on ühine alusstruktuur.

Rühmad on abstraktsemad kui graafikud, kuid neid saab siiski võrrelda isomorfismiga. Rühm on kogum elemente — näiteks numbreid —, mida saab mõne toimingu järgi omavahel kombineerida nii, et kogus on ka tulemus. Näiteks võib teil olla rühm, mille elemendid on täisarvud – kõik positiivsed ja negatiivsed täisarvud pluss null – ja mille toiming on liitmine: lisage suvalised kaks täisarvu ja tulemuseks on alati mõni teine ​​täisarv.

Kaks rühma on isomorfsed, kui saate siduda iga elemendi ühes rühmas teise elemendiga, nii et esimese rühma kahe elemendiga töötamise tulemus on kooskõlas nende elementide samaväärsete väärtustega töötamise tulemusega teises rühmas. Grupp.

Siin on lihtne näide kahest rühmast, millest igaühel on kaks elementi, mis on üksteise suhtes isomorfsed. Esimene rühm koosneb numbritest 0 ja 1 ning teine ​​rühm tähtedest a ja b. Mõlemad rühmad sisaldavad toimingut rühma elementide konkreetsel viisil kombineerimiseks, mille tulemused on toodud allolevates tabelites.

Rühmad on isomorfsed, kuna 0 paari koos a, 1 paar koos b, ja elementide kombineerimisel tekkiv struktuurne seos on mõlemas rühmas sama.

"Me ütleme, et kaks rühma on isomorfsed, kui need on põhimõtteliselt samaväärsed," ütles Sun.

Tasakaalustamata areng

Isomorfism on matemaatikas oluline mõiste – kus graafikud ja rühmad on laialdaselt esindatud –, kuna see võimaldab matemaatikutel vaadata mööda pinnapealsetest erinevustest ja keskenduda sellele, kuidas seotud objektid võivad tegelikult olla samad. Kuid see on põhiline ka arvutiteaduses; teadlased ei otsi mitte ainult algoritme, mis määravad, kas kaks objekti on isomorfsed, vaid mõõdavad ka seda, kui kiiresti need algoritmid töötavad.

See mõõtmine võib olla keeruline. Algoritmi kiirus põhineb sellel, kuidas selle käitusaeg muutub koos objektide suurusega, millega see töötab. Kujutage näiteks ette, et teil on kaks paari rühma. Ühes paaris sisaldab iga rühm viit elementi. Teises sisaldab iga rühm 10 elementi.

Eeldate, et algoritmil kulub rohkem aega, et teha kindlaks, kas rohkemate elementidega rühmad on isomorfsed. Aga kui palju veel aega? Kas see võtab kaks korda kauem aega? 5² kauem? 2⁵ kauem? Need küsimused vastavad algoritmilise kiiruse olulistele laiale klassifikatsioonile: need võivad töötada lineaarses ajas (mis tähendab antud juhul, et selleks kulub kaks korda kauem), polünoomilises ajas (5² pikem) ja eksponentsiaalne aeg (2⁵ kauem).

Arvutiteadlased teavad, millisesse kiiruskategooriasse enamik arvutusküsimusi kuulub, kuid mitte kõik.

"Enamik neist on kas kõige lihtsamad või raskeimad [tüüpi küsimus], kuid siiski on mitmeid erandeid, mis on teadmata," ütles Sun. Graafik ja rühma isomorfism on nende erandite hulgas, mis muudab need nii ahvatlevaks uurimiseks.

In 1970s, Robert Tarjan Princetoni ülikoolist mõistis, et on olemas algoritm, mis suudab kindlaks teha, kas kaks rühma on isomorfsed käitusajaga $latex n^{{(log,n)}}$, kus n on elementide arv igas rühmas. Seda nimetatakse kvaasipolünoomilise aja algoritmiks ja käitusaegade hierarhias on see parem kui eksponentsiaalne aeg (2ⁿ), kuid hullem kui polünoomaeg (n²). See on ligikaudu sama kiirus kui Babai graafi isomorfismi algoritm ja see on endiselt parim, mida saame rühmade jaoks peaaegu 50 aastat hiljem teha.

"See tähendab, et poole sajandi jooksul pole edusamme olnud," ütles Sun.

Tarjani tulemuse tegemise ajal uuriti rühma isomorfismi probleemi laiemalt kui graafilist versiooni. See on tänapäeval ümber pööratud, osaliselt seetõttu, et graafiline isomorfism on ärgitanud põnevaid uuendusi, samas kui rühmaisomorfism on seiskunud.

"Kõik meie tööriistad on aastaid olnud väga aeglased ja on olnud raske ära kasutada seda, mida me [rühmade] algebra kohta teame," ütles ta. James Wilson Colorado osariigi ülikoolist.

Kuid vaatamata sellele erinevusele, on neil kahel probleemil sügavam seos kui nende nimede sarnasus: rühma isomorfismi probleem (vähemalt selles sõnastuses) taandub graafi isomorfismi probleemiks. See tähendab, et mis tahes algoritm, mis suudab lahendada graafikuülesande, suudab sarnase ajaga lahendada ka rühmaülesande. Vastupidine pole tõsi – rühmas edenemine ei tähenda edenemist graafikul. Kuid edusammude puudumine rühmaprobleemi lahendamisel on kaalunud matemaatikuid, kes otsivad graafikuprobleemi osas proportsionaalset kasu. Kuidas saate teha raskemat asja, kui te ei saa esmalt midagi, mis on tihedalt seotud ja tundub veelgi lihtsam?

"Teisisõnu," ütles Sun, "et graafiku isomorfismi veelgi parandada, on rühma isomorfism suur kitsaskoht."

Probleem muudetud

Kui probleemi lahendamine peatub sama kaua kui rühmaisomorfismi puhul, on probleemi lahendamiseks tavaliselt vaja leiutada. "Kui teil on suur edasiminek, peaks see olema märk sellest, et on uus idee," ütles Grochow.

Suni töö sisaldab mõningaid ideid, mis hõlmavad olulist tüüpi rühma sihtimist ja nutika viisi leidmist, kuidas need rühmad tükkideks jagada, et neid võrrelda.

Nimetatakse rühmi, mille jaoks Päikese algoritm töötab p-klassi 2 ja eksponendi rühmad p. Need on sarnased rühmadele, milles kahe elemendi korrutis on teine ​​element ja korrutis jääb samaks, sõltumata nende korrutamise järjekorrast. Kuid tegelikult on oluline see, mida nad esindavad üldise rühma isomorfismi probleemi jaoks. Nendel rühmadel on väga lihtne struktuur, mis tähendab, et neid peaks olema lihtne võrrelda. Kuid vaatamata sellele lihtsusele ei olnud teadlased leidnud viisi, kuidas algoritmi kiirendada. Kuni nad seda suutsid, tundus lootusetu teha parandusi üldise rühma isomorfismi küsimuses.

Sun alustas seadistuse ümberlülitamisega rühmadelt maatriksitele, arvude massiividele, mis toimivad lineaarse algebra põhiobjektidena. See oli võimalik tänu 1930. aastatest pärit teoreemile, mida nimetatakse Baeri kirjavahetuseks, mis muudab selle rühma isomorfismi küsimuse versiooni täiesti analoogseks maatriksite probleemiks. Eelkõige töötas Sun maatriksiruumidega, mis on maatriksite kogumid, millel on eriline omadus: (lineaarne) kombinatsioon kahest ruumis olevast maatriksist võrdub teise maatriksiga ruumis.

Teisisõnu, need ruumid on üles ehitatud sarnaselt rühmadele. Selle asemel, et mõista, millal kaks rühma on isomorfsed, võiks Sun lihtsalt proovida mõista, millal kaks maatriksiruumi on isomeetrilised – maatriksiruumide isomorfismi mõiste, mis vastab rühmade omale.

Sun ei olnud esimene teadlane, kes selle lähenemisviisi kasutusele võttis, kuid ta oli esimene, kes tutvustas täiendavat sammu: maatriksruumi jagamist kaheks osaks. Üks tükk on ruumi tuum, milles kõik maatriksid on lihtsad. Teine tükk on seda südamikku ümbritsev ruum, milles kõik maatriksid on eriti keerulised. See käik vastab rühma jagamisele alamrühmadeks, mis sisaldavad ainult mõnda kogu elementi.

Seejärel rakendas Sun igale tükile erinevaid algoritmilisi meetodeid. Südamikul on lihtne struktuur, nii et ta kasutas struktuuri iseloomustust, et seda paremini organiseeritud kujul esitada. Väliskiht on keerulisem, seega pole ilmselgelt kiiret viisi selle teisega võrrelda. Selle asemel kasutab Suni meetod lähenemist, mida nimetatakse individualiseerimiseks ja täpsustamiseks, et välistada enamik võimalikke viise ühe välimise kihi kaardistamiseks teisele, ja seejärel kasutatakse arvutit kõigi ülejäänud võimalike viiside läbitöötamiseks, et teha kindlaks, kas isomorfne sobivus on olemas.

Meetod on oma olemuselt sarnane sellega, kuidas saate lahendada sudokut. Mõned ruudud, mille potentsiaalseid väärtusi piirab see, mida te juba teate (maatriksiruumi tuum), mis võimaldab teil neid kiiresti täita. Siis on ka teisi (välimine kiht), millel on vähem piiranguid, kuid mille saate aru saada lihtsalt kõiki võimalikke väärtusi proovides – ja seni, kuni selliseid ruute pole liiga palju, saate mõistatuse lahendada mõistlik aeg.

"Ma täidan kõik asjad, mida saan kiiresti öelda, et need on piiratavad, ja nüüd võin minna tagasi ja proovida puuduvate kastide kallal oma südant proovida," ütles Wilson. "Kui olete ulatust kitsendanud, on nüüd hea aeg käike vahetada ja arvuti abil õigeid väärtusi otsida."

Päikese läbimurre näitas, et seda tükeldamist on alati võimalik teha maatriksiruumide jaoks, mis vastavad p-klassi 2 ja eksponendi rühmad p. Seejärel tõestas ta, et pärast sellist jagamist võimaldab algoritmiliste tehnikate kombinatsioon määrata, kas kaks tühikut on $lateksi n^{{(log,n)}^{5/6}}$ aja jooksul isomorfsed, mis on väärtus, mis on veidi madalam kui Tarjani $latex n^{{(log,n)}}$ meetod. (Mõlemad algoritmid sisaldavad ka konstantseid termineid, millel ei ole tööajale suurt mõju ja mis oleme selguse huvides välja jätnud.)

Tulemus ei määra, millisesse kiiruskategooria rühma isomorfism kuulub; see on ikka kuskil eksponentsiaalse ja polünoomilise aja vahepeal. Kuid Sun on selle asja polünoomilisele poolele pisut lähemale nihutanud ja on põhjust arvata, et rohkem kui see võimalik peaks olema. Lõppude lõpuks pakub tema töö arvutiteadlastele kiiremat rühma isomorfismi algoritmi kõige raskemate rühmade jaoks, suurendades võimalust, et sarnane kiirus võib olla igat tüüpi rühmade jaoks käeulatuses.

"Kui suudate selle lahendada p-rühmad, tõenäoliselt saate kogu asja lahendada," ütles Grochow. "Võib olla."