Tietojenkäsittelytieteilijät tuumaa lähempänä pääalgoritmista tavoitetta | Quanta-lehti

Jos joku pyytää sinua määrittämään, ovatko kaksi objektia samoja, se saattaa tuntua triviaalilta pyynnöltä. Useimmissa jokapäiväisissä tapauksissa nopea silmäys riittää tekemään tarkan arvion.

Mutta tietojenkäsittelytieteessä se on paljon koskettavampi kysymys. Itse asiassa se leikkaa ratkaisemattoman ytimen siitä, mihin tietokoneet pystyvät. Riippuen siitä, mitä objektit ovat ja miten määrittelet samanlaisuuden, emme vieläkään tiedä, voivatko tietokoneet vastata kysymykseen nopeasti vai ovatko hidas ja työläs lähestymistapa pohjimmiltaan paras, mitä ne voivat hallita.

Viimeisen vuosikymmenen aikana on saatu joitakin tärkeitä tuloksia, jotka osoittavat, että tietokoneet voivat tehdä ainakin hieman parempaa. Yksi viime aikojen suurimmat tulokset Tietojenkäsittelytieteessä oli nopeampi algoritmi määrittää, milloin kaksi kuvaajaa ovat samat. Vuoden 2015 teos, kirjoittaja László Babai Chicagon yliopiston opiskelija rikkoi yhden tärkeän laskennallisen nopeusesteen, mutta jäi toisesta.

Nyt lehti Xiaorui Sun University of Illinois, Chicago on esittänyt uuden, nopeamman algoritmin liittyvään kysymykseen nimeltä ryhmäisomorfismin ongelma, jossa on kyse tiedosta, milloin kaksi matemaattista objektia, joita kutsutaan ryhmiksi, ovat samat. Teos, julkaistu verkossa viime maaliskuussa, ottaa pienen askeleen kohti objektien vertailun taustalla olevan laskennallisen monimutkaisuuden selventämistä.

Sunin työ rikkoo pitkäaikaisen nopeusrajoituksen tietylle ryhmäluokalle, jota pidetään ryhmän isomorfismiongelman vaikeimpana ratkaistavana esimerkkinä. Jos algoritmi pystyy nopeasti vertailemaan tämän tyyppisiä ryhmiä, on toivottavaa, että se pystyy nopeasti vertailemaan kaikentyyppisiä ryhmiä.

"Emme tunne tällaista lausetta, mutta meillä on syytä uskoa, että jonkin sellaisen pitäisi olla totta", sanoi Josh Grochow Coloradon yliopistosta, Boulderista.

Vertailu Vertailut

Jotta voit määrittää, ovatko kaksi asiaa täsmälleen samoja, sinun on ensin määritettävä "sama". Kahta numerosarjaa voidaan pitää samana, jos ne sisältävät vain samat numerot, tai niissä saatetaan tarvita samat numerot samassa järjestyksessä.

Isomorfismi on erityinen samankaltaisuus, jota tulee paljon esiin matematiikassa. Kun kaksi objektia ovat isomorfisia keskenään, se tarkoittaa karkeasti, että ne sisältävät samat elementit ja että nämä elementit ovat samassa suhteessa toisiinsa.

Graafit – kokoelmat kärkipisteitä (pisteitä), jotka on yhdistetty reunoilla (viivoilla) – tarjoavat helppokäyttöisen, visuaalisen tavan nähdä, miltä isomorfismi voi näyttää. Kaksi graafia ovat isomorfisia, jos voit sovittaa toisen graafin kärjet toisen pisteisiin siten, että kärjet, jotka on yhdistetty reunalla ensimmäisessä graafissa, yhdistetään toisessa. Isomorfiset kuvaajat voivat näyttää erilaisilta pinnalla, mutta niillä on yhteinen taustarakenne.

Ryhmät ovat abstrakteja kuin graafit, mutta niitä voidaan silti verrata isomorfismilla. Ryhmä on kokoelma elementtejä, kuten numeroita, joita voidaan yhdistää jonkin toiminnon mukaan niin, että tulos on myös kokoelmassa. Sinulla voi olla esimerkiksi ryhmä, jonka elementit ovat kokonaislukuja – kaikki positiiviset ja negatiiviset kokonaisluvut plus nolla – ja jonka toiminta on yhteenlasku: Lisää mitkä tahansa kaksi kokonaislukua, ja tuloksena on aina toinen kokonaisluku.

Kaksi ryhmää ovat isomorfisia, jos voit yhdistää jokaisen elementin toisessa ryhmässä toisen elementin kanssa siten, että kahden ensimmäisen ryhmän elementin käyttämisen tulos on yhdenmukainen toisen ryhmän näiden elementtien vastaavilla arvoilla käyttämisen tuloksen kanssa. ryhmä.

Tässä on yksinkertainen esimerkki kahdesta ryhmästä, joissa kummassakin on kaksi elementtiä, jotka ovat isomorfisia keskenään. Ensimmäinen ryhmä koostuu numeroista 0 ja 1, ja toinen ryhmä koostuu kirjaimista a ja b. Molemmissa ryhmissä on operaatio ryhmän elementtien yhdistämiseksi tietyllä tavalla, jonka tulokset esitetään alla olevissa taulukoissa.

Ryhmät ovat isomorfisia, koska 0 paria kanssa a, 1 paria b, ja elementtien yhdistämisen tuottama rakenteellinen suhde on sama molemmissa ryhmissä.

"Sanomme, että kaksi ryhmää ovat isomorfisia, jos ne ovat periaatteessa vastaavia", Sun sanoi.

Epätasapainoinen kehitys

Isomorfismi on tärkeä käsite matematiikassa – jossa kaavioita ja ryhmiä esiintyy laajasti – koska sen avulla matemaatikot voivat tarkastella pinnallisia eroja ja keskittyä tapoihin, joilla toisiinsa liittyvät objektit voivat todella olla samoja. Mutta se on perustavanlaatuista myös tietojenkäsittelytieteessä; Tutkijat eivät vain etsi algoritmeja, jotka määrittävät, ovatko kaksi objektia isomorfisia, vaan myös mittaavat, kuinka nopeasti nämä algoritmit voivat toimia.

Tuo mittaus voi olla hankala. Algoritmin nopeus perustuu siihen, kuinka sen ajonaika muuttuu työskenneltyjen objektien koon mukaan. Kuvittele esimerkiksi, että sinulla on kaksi paria ryhmiä. Yhdessä parissa jokainen ryhmä sisältää viisi elementtiä. Toisessa jokaisessa ryhmässä on 10 elementtiä.

Oletat, että algoritmilta kuluu enemmän aikaa määrittääkseen, ovatko ryhmät, joissa on enemmän elementtejä, isomorfisia. Mutta kuinka paljon aikaa vielä? Kestääkö se kaksi kertaa kauemmin? 5² kauemmin? 2⁵ kauemmin? Nämä kysymykset vastaavat algoritmisen nopeuden tärkeitä laajoja luokituksia: Ne voivat suorittaa lineaarisessa ajassa (mikä tarkoittaa tässä tapauksessa, että se kestää kaksi kertaa kauemmin), polynomiajassa (5² pidempi) ja eksponentiaalinen aika (2⁵ kauemmin).

Tietojenkäsittelytieteilijät tietävät, mihin nopeusluokkaan useimmat tietojenkäsittelykysymykset kuuluvat, mutta eivät kaikki.

"Useimmat ovat joko helpoimpia tai vaikeimpia [tyyppinen kysymys], mutta silti on useita poikkeuksia, jotka ovat tuntemattomia", Sun sanoi. Graafi ja ryhmäisomorfismi ovat näitä poikkeuksia, mikä tekee niistä niin houkuttelevia tutkia.

1970-luvulla Robert Tarjan Princetonin yliopistosta ymmärsivät, että on olemassa algoritmi, joka voi määrittää, ovatko mitkään kaksi ryhmää isomorfisia ja joiden suoritusaika on $latex n^{{(log,n)}}$, missä n on kunkin ryhmän elementtien lukumäärä. Tätä kutsutaan kvasipolynomi-aika-algoritmiksi, ja suoritusaikojen hierarkiassa se on parempi kuin eksponentiaalinen aika (2ⁿ) mutta huonompi kuin polynomiaika (n²). Tämä on suunnilleen sama nopeus kuin Babain graafisomorfismialgoritmi, ja se on edelleen parasta, mitä voimme tehdä ryhmille lähes 50 vuotta myöhemmin.

"Se tarkoittaa karkeasti sitä, ettei edistystä ole tapahtunut puoleen vuosisataan", Sun sanoi.

Tarjanin tuloksen aikaan ryhmäisomorfismiongelmaa tutkittiin laajemmin kuin graafiversiota. Se on käännetty tänään, osittain siksi, että graafisomorfismi on kannustanut jännittäviä innovaatioita, kun taas ryhmäisomorfismi on pysähtynyt.

"Kaikki työkalumme ovat olleet todella hitaita vuosia, ja on ollut vaikeaa hyödyntää sitä, mitä tiedämme [ryhmien] algebrasta", sanoi. James Wilson Coloradon osavaltion yliopistosta.

Mutta tästä erosta huolimatta näillä kahdella ongelmalla on syvempi yhteys kuin niiden nimien samankaltaisuus: Ryhmäisomorfismiongelma (ainakin tässä formulaatiossa) pelkistyy graafisomorfismiongelmaksi. Tämä tarkoittaa, että mikä tahansa algoritmi, joka voi ratkaista kuvaajatehtävän, voi myös ratkaista ryhmätehtävän samassa ajassa. Päinvastoin ei pidä paikkaansa – ryhmän edistyminen ei tarkoita edistymistä kaaviossa. Mutta edistyksen puute ryhmäongelmassa on painanut matemaatikot, jotka etsivät suhteellisia hyötyjä graafi-ongelmasta. Kuinka voit saavuttaa vaikeamman asian, jos et voi ensin saavuttaa jotain, joka liittyy läheisesti ja näyttää vieläkin helpommalta?

"Toisin sanoen", Sun sanoi, "jos haluat parantaa edelleen graafisomorfismia, ryhmäisomorfismi on suuri pullonkaula."

Ongelma muutettu

Kun ongelman eteneminen pysähtyy yhtä kauan kuin ryhmäisomorfismissa, keksinnöstä on yleensä tarpeen päästä eroon. "Kun sinulla on suuri edistysaskel, sen pitäisi olla merkki siitä, että on olemassa uusi idea", Grochow sanoi.

Sunin työ sisältää muutamia ideoita, joihin liittyy kohdistaminen tärkeän tyyppiseen ryhmään ja näppärän tavan jakaminen näiden ryhmien osiin, jotta niitä voidaan vertailla.

Ryhmiä, joille Sunin algoritmi toimii, kutsutaan p-luokan 2 ja eksponentin ryhmät p. Ne ovat samanlaisia ​​kuin ryhmiä, joissa kahden elementin tulo on toinen elementti ja tulo pysyy samana riippumatta siitä, missä järjestyksessä ne kerrotaan. Mutta todella tärkeää on se, mitä ne edustavat koko ryhmän isomorfismiongelmalle. Näillä ryhmillä on hyvin yksinkertainen rakenne, mikä tarkoittaa, että niitä on helppo verrata. Mutta tästä yksinkertaisuudesta huolimatta tutkijat eivät olleet keksineet tapaa nopeuttaa algoritmia. Ennen kuin he pystyivät, tuntui toivottomalta tehdä parannuksia yleiseen ryhmäisomorfismiin.

Sun aloitti vaihtamalla asetuksen ryhmistä matriiseihin, lukutaulukoihin, jotka toimivat lineaarisen algebran perusobjekteina. Tämä oli mahdollista 1930-luvun Baer-vastaavuuden lauseen ansiosta, joka muuttaa tämän version ryhmäisomorfismikysymyksestä täysin analogiseksi matriiseja koskevaksi ongelmaksi. Erityisesti Sun työskenteli matriisiavaruuksien kanssa, jotka ovat matriisikokoelmia, joilla on erityinen ominaisuus: Minkä tahansa kahden matriisin (lineaarinen) yhdistelmä avaruudessa vastaa toista matriisia avaruudessa.

Toisin sanoen nämä tilat ovat rakenteeltaan paljon kuin ryhmät. Sen sijaan, että yrittäisi ymmärtää, milloin kaksi ryhmää ovat isomorfisia, Sun voisi vain yrittää ymmärtää, milloin kaksi matriisiavaruutta ovat isometrisiä - käsite matriisiavaruuksien isomorfismista, joka vastaa ryhmien isomorfismin käsitettä.

Sun ei ollut ensimmäinen tutkija, joka omaksui tämän lähestymistavan, mutta hän oli ensimmäinen, joka esitteli lisävaiheen: matriisiavaruuden jakamisen kahteen osaan. Yksi pala on tilan ydin, jossa kaikki matriisit ovat yksinkertaisia. Toinen osa on sitä ydintä ympäröivä tila, jossa kaikki matriisit ovat erityisen monimutkaisia. Tämä siirto vastaa ryhmän jakamista alaryhmiin, jotka sisältävät vain osan kokonaiselementeistä.

Sun sovelsi sitten erilaisia ​​algoritmisia menetelmiä kuhunkin näistä kappaleista. Ytimellä on yksinkertainen rakenne, joten hän käytti rakenteen luonnehdintaa esittääkseen sen organisoidummin. Ulompi kerros on monimutkaisempi, joten ei ole ilmeisen nopeaa tapaa verrata sitä toiseen. Sen sijaan Sunin menetelmä käyttää lähestymistapaa, jota kutsutaan individualisoinniksi ja tarkentamiseksi, sulkemaan pois useimmat mahdolliset tavat kartoittaa yksi ulkokerros toiseen ja käyttää sitten tietokonetta kaikkien jäljellä olevien mahdollisten tapojen selvittämiseksi, onko isomorfinen yhteensopivuus olemassa.

Menetelmä on hengeltään samanlainen kuin kuinka ratkaista sudoku-pulma. On joitakin neliöitä, joiden potentiaalisia arvoja rajoittaa se, mitä jo tiedät (matriisiavaruuden ydin), joten voit täyttää ne nopeasti. Sitten on muita (ulompi kerros), joilla on vähemmän rajoituksia, mutta jotka voit selvittää vain kokeilemalla kaikkia mahdollisia arvoja – ja niin kauan kuin tällaisia ​​neliöitä ei ole liikaa, voit silti ratkaista pulman kohtuullisen ajan.

"Täytän kaikki asiat, jotka voin nopeasti kertoa, että ne ovat rajoitettuja, ja nyt saatan palata sisään ja kokeilla sydäntäni puuttuvien laatikoiden suhteen", Wilson sanoi. "Jos olet kaventunut, nyt on hyvä aika vaihtaa vaihdetta ja etsiä oikeita arvoja tietokoneen avulla."

Sunin läpimurto osoitti, että tämä jako on aina mahdollista tehdä matriisiavaruuksille, jotka vastaavat p-luokan 2 ja eksponentin ryhmät p. Sitten hän osoitti, että tällaisen jaon jälkeen algoritmisten tekniikoiden yhdistelmä mahdollistaa sen määrittämisen, ovatko kaksi avaruutta isomorfisia $lateksi n^{{(log,n)}^{5/6}}$ ajassa, arvo, joka on hieman pienempi kuin Tarjanin $lateksi n^{{(log,n)}}$-menetelmä. (Molemmat algoritmit sisältävät myös vakiotermejä, joilla ei ole suurta vaikutusta suoritusaikaan ja jotka olemme jättäneet selvyyden vuoksi pois.)

Tulos ei määritä mihin nopeusluokkaryhmään isomorfismi kuuluu; se on edelleen jossain eksponentiaalisen ja polynomiajan välissä. Mutta Sun on työntänyt sitä hieman lähemmäksi asioiden polynomipuolta, ja on syytä uskoa, että enemmän kuin sen pitäisi olla mahdollista. Loppujen lopuksi hänen työnsä tarjoaa tietojenkäsittelytieteilijöille nopeamman ryhmäisomorfismi-algoritmin vaikeimmille ryhmille, mikä lisää mahdollisuutta, että samanlainen vauhti voisi olla kaikenlaisten ryhmien ulottuvilla.

"Jos voit ratkaista sen p-ryhmät, luultavasti voit ratkaista koko asian”, Grochow sanoi. "Voi olla."