Informatikere nærmer seg store algoritmiske mål | Quanta Magazine

Hvis noen ber deg om å finne ut om to objekter er like, kan det virke som en triviell forespørsel. I de fleste dagligdagse tilfeller er et raskt blikk nok til at du kan avgi en nøyaktig vurdering.

Men i informatikk er det et langt mer involvert spørsmål. Faktisk er det en som skjærer til det uavklarte hjertet av hva datamaskiner er i stand til. Avhengig av hva objektene er, og hvordan du definerer likhet, vet vi fortsatt ikke om datamaskiner kan svare raskt på spørsmålet, eller om en langsom og arbeidskrevende tilnærming i hovedsak er det beste de kan håndtere.

I løpet av det siste tiåret har det vært noen viktige resultater som viser at datamaskiner i det minste kan gjøre det litt bedre enn det. En av største siste resultatene i informatikk var en raskere algoritme for å bestemme når to grafer er like. 2015-arbeidet, av László Babai fra University of Chicago, brøt en viktig beregningshastighetsbarriere, men kom til kort en annen.

Nå, et papir av Xiaorui Sun fra University of Illinois, Chicago har presentert en ny, raskere algoritme for et relatert spørsmål kalt gruppeisomorfismeproblemet, som handler om å vite når to matematiske objekter kalt grupper er like. Verket, lagt ut på nett siste mars, tar et lite skritt mot å klargjøre den underliggende beregningskompleksiteten som er involvert i å sammenligne objekter.

Suns arbeid bryter en langvarig fartsgrense for en bestemt gruppe grupper - den som anses som den vanskeligste forekomsten av gruppeisomorfismeproblemet å løse. Hvis en algoritme raskt kan sammenligne grupper av denne typen, er håpet at den raskt kan sammenligne grupper av enhver type.

"Vi kjenner ikke til et slikt teorem, men vi har grunn til å tro at noe slikt burde være sant," sa Josh Grochow ved University Colorado, Boulder.

Sammenligning av sammenligninger

For å finne ut om to ting er like på en presis måte, må du først definere "det samme." To tallstrenger kan betraktes som like hvis de bare inneholder de samme sifrene, eller de må kanskje ha de samme sifrene i samme rekkefølge.

Isomorfisme er en spesiell type likhet som kommer opp mye i matematikk. Når to objekter er isomorfe for hverandre, betyr det omtrent at de inneholder de samme elementene, og at disse elementene er i samme forhold til hverandre.

Grafer - samlinger av hjørner (prikker) koblet sammen med kanter (linjer) - gir en tilgjengelig, visuell måte å se hvordan isomorfisme kan se ut. To grafer er isomorfe hvis du kan matche toppunkter i en graf med toppunkter i den andre, slik at toppunkter som er forbundet med en kant i den første grafen er forbundet med en kant i den andre. Isomorfe grafer kan se annerledes ut på overflaten, men de deler en underliggende struktur.

Grupper er mer abstrakte enn grafer, men de er fortsatt tilgjengelige for sammenligning ved isomorfisme. En gruppe er en samling av elementer — for eksempel tall — som kan kombineres med hverandre i henhold til en operasjon slik at resultatet også er i samlingen. For eksempel kan du ha en gruppe hvis elementer er heltall - alle positive og negative hele tall, pluss null - og hvis operasjon er addisjon: Legg til to heltall, og resultatet er alltid et annet heltall.

To grupper er isomorfe hvis du kan pare hvert element i en gruppe med et element i den andre, slik at resultatet av å operere på to elementer i den første gruppen er konsistent med resultatet av å operere på de ekvivalente verdiene til disse elementene i den andre gruppe.

Her er et enkelt eksempel på to grupper, hver med to elementer, som er isomorfe for hverandre. Den første gruppen består av tallene 0 og 1, og den andre gruppen består av bokstavene a og b. Begge gruppene inneholder en operasjon for å kombinere elementene i gruppen på en bestemt måte, med resultatene angitt i tabellene nedenfor.

Gruppene er isomorfe fordi 0 parer med a, 1 par med b, og det strukturelle forholdet produsert ved å kombinere elementer er det samme i begge grupper.

"Vi sier at to grupper er isomorfe hvis de i utgangspunktet er likeverdige," sa Sun.

Ubalansert fremgang

Isomorfisme er et viktig konsept i matematikk - der grafer og grupper har mye å gjøre - fordi det lar matematikere se forbi overfladiske forskjeller og fokusere på måtene relaterte objekter faktisk kan være de samme. Men det er grunnleggende i informatikk også; forskere ser ikke bare etter algoritmer som bestemmer om to objekter er isomorfe, men måler også hvor raskt disse algoritmene kan kjøre.

Den målingen kan være vanskelig. En algoritmes hastighet er basert på hvordan kjøretiden endres med størrelsen på objektene den jobber med. Tenk deg for eksempel at du har to par med grupper. I ett par inneholder hver gruppe fem elementer. I den andre inneholder hver gruppe 10 elementer.

Du forventer at det tar en algoritme lenger tid å bestemme om gruppene med flere elementer er isomorfe. Men hvor mye mer tid? Vil det ta dobbelt så lang tid? 5² lengre? 2⁵ lengre? Disse spørsmålene tilsvarer viktige brede klassifikasjoner av algoritmisk hastighet: De kan kjøres i lineær tid (som i dette tilfellet betyr at det tar dobbelt så lang tid), polynomtid (5² lengre) og eksponentiell tid (2⁵ lengre).

Dataforskere vet hvilken hastighetskategori de fleste dataspørsmål faller inn under, men ikke alle.

"De fleste er enten de enkleste eller de vanskeligste [spørsmålene], men det er fortsatt flere unntak som er ukjente," sa Sun. Graf- og gruppeisomorfisme er blant disse unntakene, noe som gjør dem så attraktive å studere.

I 1970s, Robert Tarjan fra Princeton University innså at det er en algoritme som kan bestemme om to grupper er isomorfe med en kjøretid på $latex n^{{(log,n)}}$, der n er antall elementer i hver gruppe. Dette kalles en kvasi-polynomisk-tidsalgoritme, og i hierarkiet av kjøretider er det bedre enn eksponentiell tid (2ⁿ) men verre enn polynomtid (n²). Dette er omtrent samme hastighet som Babais grafisomorfismealgoritme, og det er fortsatt det beste vi kan gjøre for grupper nesten 50 år senere.

"Det betyr omtrent at det ikke har vært noen fremgang på et halvt århundre," sa Sun.

På tidspunktet for Tarjans resultat ble gruppeisomorfismeproblemet mer studert enn grafversjonen. Det er snudd i dag, delvis fordi grafisomorfisme har ansporet til spennende innovasjoner mens gruppeisomorfisme har stoppet opp.

"Alle verktøyene våre har vært veldig trege i årevis, og det har vært vanskelig å utnytte det vi vet om algebraen [av grupper]," sa James Wilson ved Colorado State University.

Men til tross for denne ulikheten i fremdriften, har de to problemene en dypere sammenheng enn likheten mellom navnene deres: Gruppeisomorfismeproblemet (i hvert fall i denne formuleringen) reduseres til grafisomorfismeproblemet. Dette betyr at enhver algoritme som kan løse grafoppgaven også kan løse gruppeoppgaven på tilsvarende tid. Det motsatte er ikke sant - fremgang på gruppe betyr ikke fremgang på grafen. Men mangelen på fremskritt i gruppeproblemet har tynget matematikere som søker tilsvarende gevinster på grafproblemet. Hvordan kan du oppnå en vanskeligere ting hvis du ikke først kan oppnå noe som er nært beslektet og virker enda enklere?

"Med andre ord," sa Sun, "for ytterligere å forbedre grafisomorfisme, er gruppeisomorfisme en stor flaskehals."

Et problem forvandlet

Når fremskritt på et problem stopper så lenge som det gjorde for gruppeisomorfisme, er oppfinnelsen vanligvis nødvendig for å løse seg. "Når du har et stort fremskritt, bør det være en indikasjon på at det er en ny idé," sa Grochow.

Suns arbeid inneholder noen ideer som involverer målretting mot en viktig type gruppe og finne en smart måte å dele disse gruppene i biter for å sammenligne dem.

Gruppene Suns algoritme fungerer for kalles p-grupper av klasse 2 og eksponent p. De ligner grupper der produktet av to elementer er et annet element og produktet forblir det samme uavhengig av rekkefølgen du multipliserer dem i. Men det som virkelig betyr noe er hva de representerer for det overordnede gruppeisomorfismeproblemet. Disse gruppene har en veldig enkel struktur, som betyr at de skal være enkle å sammenligne. Men til tross for denne enkelheten, hadde forskerne ikke funnet ut en måte å øke hastigheten på algoritmen. Inntil de kunne, føltes det håpløst å gjøre forbedringer for det generelle spørsmålet om gruppeisomorfisme.

Sun begynte med å bytte innstillingen fra grupper til matriser, matriser av tall som fungerer som grunnleggende objekter i lineær algebra. Dette var mulig på grunn av et teorem fra 1930-tallet kalt Baer-korrespondansen, som forvandler denne versjonen av gruppeisomorfismespørsmålet til et perfekt analogt problem om matriser. Spesielt jobbet Sun med matriserom, som er samlinger av matriser med en spesiell egenskap: Den (lineære) kombinasjonen av to matriser i rommet tilsvarer en annen matrise i rommet.

Disse rommene er med andre ord strukturert mye som grupper. Så i stedet for å prøve å forstå når to grupper er isomorfe, kan Sun bare prøve å forstå når to matriserom er isometriske - en forestilling om isomorfisme av matriserom som tilsvarer gruppens.

Sun var ikke den første forskeren som tok i bruk denne tilnærmingen, men han var den første som introduserte et ekstra trinn: å dele et matriserom i to deler. Ett stykke er kjernen i rommet, der alle matrisene er enkle. Den andre delen er rommet rundt den kjernen, der alle matrisene er spesielt komplekse. Dette trekket tilsvarer å dele en gruppe i undergrupper som bare inneholder noen av de totale elementene.

Sun brukte deretter forskjellige algoritmiske metoder på hver av disse delene. Kjernen har en enkel struktur, så han brukte en karakterisering av strukturen for å representere den på en mer organisert måte. Det ytre laget er mer komplekst, så det er ingen åpenbart rask måte å sammenligne det med et annet. I stedet bruker Suns metode en tilnærming som kalles individualisering og foredling for å utelukke de fleste av de mulige måtene å kartlegge ett ytre lag på det andre, og bruker deretter en datamaskin til å jobbe gjennom alle gjenværende mulige måter å avgjøre om en isomorf matching eksisterer.

Metoden er lik hvordan du kan løse et sudoku-puslespill. Det er noen firkanter hvis potensielle verdier er begrenset av det du allerede vet (kjernen i matriserommet), slik at du kan fylle dem ut raskt. Så er det andre (det ytre laget) som har færre begrensninger, men som du kan finne ut bare ved å prøve alle mulige verdier - og så lenge det ikke er for mange av denne typen firkanter, kan du fortsatt løse gåten i rimelig tid.

"Jeg fyller ut alle de tingene jeg raskt kan si er begrensende, og nå kan jeg gå inn igjen og prøve meg på de manglende boksene," sa Wilson. "Hvis du har begrenset omfanget, er det nå et godt tidspunkt å bytte gir og bruke datamaskinen til å søke etter de riktige verdiene."

Suns gjennombrudd viste at det alltid er mulig å gjøre denne splittingen for matriserommene som tilsvarer p-grupper av klasse 2 og eksponent p. Han beviste så at etter en slik splittelse, gjør en kombinasjon av algoritmiske teknikker det mulig å bestemme om to rom er isomorfe i $latex n^{{(log,n)}^{5/6}}$ tid, en verdi som er litt lavere enn Tarjans $latex n^{{(log,n)}}$-metode. (Begge algoritmer inkluderer også konstante termer, som ikke har stor effekt på kjøretiden, og som vi har utelatt for klarhetens skyld.)

Resultatet avgjør ikke hvilken hastighetskategori gruppe isomorfisme faller inn i; det er fortsatt et sted mellom eksponentiell og polynomisk tid. Men Sun har dyttet det litt nærmere polynomsiden av ting, og det er grunn til å tro at mer enn det burde være mulig. Tross alt gir arbeidet hans informatikere en raskere gruppeisomorfismealgoritme for den vanskeligste typen grupper, noe som øker muligheten for at en lignende hastighetsøkning kan være innen rekkevidde for grupper av alle slag.

"Hvis du kan løse det for p-grupper, sannsynligvis kan dere løse hele greia," sa Grochow. "Kan være."