Datavetare Inch Närmare det stora algoritmiska målet | Quanta Magazine

Om någon ber dig att avgöra om två objekt är samma, kan det verka som en trivial begäran. I de flesta vardagliga fall räcker det med en snabb blick för att du ska kunna göra en korrekt bedömning.

Men inom datavetenskap är det en mycket mer involverad fråga. I själva verket är det en som skär till det olösta hjärtat av vad datorer kan. Beroende på vad objekten är och hur du definierar likhet, vet vi fortfarande inte om datorer kan svara på frågan snabbt, eller om ett långsamt och mödosamt tillvägagångssätt är i grunden det bästa de kan hantera.

Under det senaste decenniet har det kommit några viktiga resultat som visar att datorer kan göra det åtminstone lite bättre än så. En av största senaste resultaten inom datavetenskap var en snabbare algoritm för att bestämma när två grafer är lika. 2015 års arbete, av László Babai från University of Chicago, bröt en viktig beräkningshastighetsbarriär men bröt en annan.

Nu en tidning av Xiaorui Sun från University of Illinois, Chicago har presenterat en ny, snabbare algoritm för en relaterad fråga som kallas gruppisomorfismproblemet, som handlar om att veta när två matematiska objekt som kallas grupper är likadana. Verket, lagt ut på nätet den senaste mars, tar ett litet steg mot att klargöra den underliggande beräkningskomplexiteten som är involverad i att jämföra objekt.

Suns arbete bryter en långvarig hastighetsgräns för en viss klass av grupper - den som anses vara den svåraste instansen av gruppen isomorfismproblem att lösa. Om en algoritm snabbt kan jämföra grupper av detta slag är förhoppningen att den snabbt kan jämföra grupper av vilken typ som helst.

"Vi känner inte till ett sådant teorem, men vi har anledning att tro att något sådant borde vara sant," sa Josh Grochow från University Colorado, Boulder.

Jämföra jämförelser

För att avgöra om två saker är lika på ett exakt sätt, måste du först definiera "detsamma." Två strängar av siffror kan anses vara lika om de bara innehåller samma siffror, eller så kan de behöva ha samma siffror i samma ordning.

Isomorfism är en speciell typ av likhet som kommer upp mycket i matematik. När två objekt är isomorfa till varandra betyder det ungefär att de innehåller samma element, och att dessa element är i samma relation med varandra.

Grafer — samlingar av hörn (punkter) länkade av kanter (linjer) — ger ett tillgängligt, visuellt sätt att se hur isomorfism kan se ut. Två grafer är isomorfa om du kan matcha hörn i en graf med hörn i den andra, så att hörn som är förbundna med en kant i den första grafen är sammankopplade med en kant i den andra. Isomorfa grafer kan se olika ut på ytan, men de delar en underliggande struktur.

Grupper är mer abstrakta än grafer, men de är fortfarande mottagliga för jämförelse med isomorfism. En grupp är en samling element — som siffror — som kan kombineras med varandra enligt någon operation så att resultatet också finns i samlingen. Till exempel kan du ha en grupp vars element är heltal — alla positiva och negativa heltal plus noll — och vars operation är addition: Lägg till två valfria heltal, och resultatet blir alltid ett annat heltal.

Två grupper är isomorfa om du kan para ihop varje element i en grupp med ett element i den andra, så att resultatet av att arbeta på två element i den första gruppen överensstämmer med resultatet av att arbeta på motsvarande värden för dessa element i den andra grupp.

Här är ett enkelt exempel på två grupper, var och en med två element, som är isomorfa till varandra. Den första gruppen består av siffrorna 0 och 1, och den andra gruppen består av bokstäverna a och b. Båda grupperna innehåller en operation för att kombinera elementen i gruppen på ett specifikt sätt, med resultaten som anges i tabellerna nedan.

Grupperna är isomorfa eftersom 0 parar med a, 1 par med b, och det strukturella förhållandet som skapas genom att kombinera element är detsamma i båda grupperna.

"Vi säger att två grupper är isomorfa om de i grunden är likvärdiga," sa Sun.

Obalanserade framsteg

Isomorfism är ett viktigt begrepp inom matematiken - där grafer och grupper är omfattande - eftersom det tillåter matematiker att se förbi ytliga skillnader och fokusera på hur relaterade objekt faktiskt kan vara desamma. Men det är grundläggande inom datavetenskap också; forskare letar inte bara efter algoritmer som avgör om två objekt är isomorfa, utan mäter också hur snabbt dessa algoritmer kan köras.

Den mätningen kan vara knepig. En algoritms hastighet baseras på hur dess körtid ändras med storleken på objekten den arbetar med. Föreställ dig till exempel att du har två par grupper. I ett par innehåller varje grupp fem element. I den andra innehåller varje grupp 10 element.

Du kan förvänta dig att det tar en algoritm längre tid att avgöra om grupperna med fler element är isomorfa. Men hur mycket mer tid? Kommer det att ta dubbelt så lång tid? 5² längre? 2⁵ längre? Dessa frågor motsvarar viktiga breda klassificeringar av algoritmisk hastighet: De kan köras i linjär tid (vilket i detta fall betyder att det tar dubbelt så lång tid), polynomtid (5² längre) och exponentiell tid (2⁵ längre).

Datavetare vet vilken hastighetskategori de flesta datorfrågor faller inom, men inte alla.

"De flesta är antingen de lättaste eller svåraste [typ av frågor], men det finns fortfarande flera undantag som är okända," sa Sun. Graf- och gruppisomorfism är bland dessa undantag, vilket är det som gör dem så tilltalande att studera.

I 1970s, Robert Tarjan vid Princeton University insåg att det finns en algoritm som kan avgöra om två grupper är isomorfa med en körtid på $latex n^{{(log,n)}}$, där n är antalet element i varje grupp. Detta kallas en kvasi-polynom-tidsalgoritm, och i hierarkin av körtider är det bättre än exponentiell tid (2ⁿ) men sämre än polynomtid (n²). Detta är ungefär samma hastighet som Babais grafisomorfismalgoritm, och det är fortfarande det bästa vi kan göra för grupper nästan 50 år senare.

"Det betyder ungefär att det inte har skett några framsteg på ett halvt sekel," sa Sun.

Vid tiden för Tarjans resultat studerades gruppen isomorfism mer omfattande än grafversionen. Det har vänt idag, delvis för att grafisomorfism har stimulerat spännande innovationer medan gruppisomorfism har avstannat.

"Alla våra verktyg har varit väldigt långsamma i åratal, och det har varit svårt att utnyttja det vi vet om algebra [av grupper]", sa James Wilson vid Colorado State University.

Men trots denna olikhet på gång har de två problemen ett djupare samband än likheten mellan deras namn: Gruppisomorfismproblemet (åtminstone i denna formulering) reduceras till grafisomorfismproblemet. Det betyder att vilken algoritm som helst som kan lösa grafproblemet också kan lösa gruppproblemet på liknande tid. Det omvända är inte sant – framsteg på grupp innebär inte framsteg på grafen. Men bristen på framsteg när det gäller gruppproblemet har tyngt matematiker som söker proportionerliga vinster på grafproblemet. Hur kan du åstadkomma en svårare sak om du inte först kan åstadkomma något som är nära besläktat och verkar ännu lättare?

"Med andra ord," sa Sun, "för att ytterligare förbättra grafisomorfism är gruppisomorfism en stor flaskhals."

Ett problem förvandlat

När framstegen på ett problem stannar så länge som det gjorde för gruppisomorfism, är uppfinningar vanligtvis nödvändiga för att lossna. "När du har ett stort framsteg borde det vara en indikation på att det finns en ny idé," sa Grochow.

Suns arbete innehåller några idéer som involverar att rikta in sig på en viktig typ av grupp och hitta ett smart sätt att dela upp dessa grupper i bitar för att jämföra dem.

De grupper som Suns algoritm fungerar för kallas p-grupper av klass 2 och exponent p. De liknar grupper där produkten av två element är ett annat element och produkten förblir densamma oavsett i vilken ordning du multiplicerar dem. Men det som verkligen betyder något är vad de representerar för det övergripande gruppen isomorfismproblem. Dessa grupper har en mycket enkel struktur, vilket gör att de ska vara lätta att jämföra. Men trots denna enkelhet hade forskarna inte kommit på något sätt att påskynda algoritmen. Tills de kunde kändes det hopplöst att göra förbättringar för den allmänna frågan om gruppisomorfism.

Sun började med att ändra inställningen från grupper till matriser, arrayer av tal som fungerar som grundobjekt i linjär algebra. Detta var möjligt tack vare en teorem från 1930-talet som kallas Baer-korrespondensen, som förvandlar denna version av gruppen isomorfismfrågan till ett helt analogt problem om matriser. Speciellt arbetade Sun med matrisrum, som är samlingar av matriser med en speciell egenskap: Den (linjära) kombinationen av två valfria matriser i rummet är lika med en annan matris i rummet.

Med andra ord är dessa utrymmen strukturerade ungefär som grupper. Så istället för att försöka förstå när två grupper är isomorfa, kunde Sun bara försöka förstå när två matrisutrymmen är isometriska - en uppfattning om isomorfism av matrisutrymmen som motsvarar den för grupper.

Sun var inte den första forskaren som använde detta tillvägagångssätt, men han var den första som introducerade ett ytterligare steg: att dela ett matrisutrymme i två delar. En bit är kärnan i utrymmet, där alla matriser är enkla. Den andra biten är utrymmet som omger den kärnan, där alla matriser är särskilt komplexa. Detta drag motsvarar att dela upp en grupp i undergrupper som bara innehåller några av de totala elementen.

Sun tillämpade sedan olika algoritmiska metoder på var och en av dessa bitar. Kärnan har en enkel struktur, så han använde en karaktärisering av strukturen för att representera den på ett mer organiserat sätt. Det yttre lagret är mer komplext, så det finns inget uppenbart snabbt sätt att jämföra det med ett annat. Istället använder Suns metod ett tillvägagångssätt som kallas individualisering och förfining för att utesluta de flesta möjliga sätten att kartlägga ett yttre skikt på det andra och använder sedan en dator för att arbeta igenom alla återstående möjliga sätt att avgöra om en isomorf matchning existerar.

Metoden liknar till sin anda hur du kan lösa ett sudoku-pussel. Det finns några rutor vars potentiella värden begränsas av vad du redan vet (kärnan i matrisutrymmet), vilket gör att du snabbt kan fylla i dem. Sedan finns det andra (det yttre lagret) som har färre begränsningar, men som du kan lista ut bara genom att prova alla möjliga värden — och så länge det inte finns för många av den här typen av rutor, kan du fortfarande lösa pusslet i en rimlig tid.

"Jag fyller i alla de saker jag snabbt kan säga är begränsade, och nu kanske jag går tillbaka in och provar mitt hjärta på de saknade lådorna," sa Wilson. "Om du har begränsat räckvidden är det nu ett bra tillfälle att växla och använda datorn för att söka efter rätt värden."

Suns genombrott visade att det alltid är möjligt att göra denna uppdelning för matrisutrymmen som motsvarar p-grupper av klass 2 och exponent p. Han bevisade sedan att efter en sådan uppdelning gör en kombination av algoritmiska tekniker det möjligt att avgöra om två utrymmen är isomorfa i $latex n^{{(log,n)}^{5/6}}$ tid, ett värde som är något lägre än Tarjans $latex n^{{(log,n)}}$-metod. (Båda algoritmerna inkluderar också konstanta termer, som inte har någon större effekt på körtiden, och som vi har utelämnat för tydlighetens skull.)

Resultatet avgör inte vilken hastighetskategori grupp isomorfism faller in i; det är fortfarande någonstans mellan exponentiell och polynomisk tid. Men Sun har knuffat det lite närmare den polynomiska sidan av saker och ting, och det finns anledning att tro att mer än så borde vara möjligt. Hans arbete förser trots allt datavetare med en snabbare gruppisomorfismalgoritm för den svåraste typen av grupper, vilket ökar möjligheten att en liknande snabbhet kan vara inom räckhåll för grupper av alla slag.

"Om du kan lösa det för p-grupper, förmodligen kan ni lösa hela grejen, sa Grochow. "Kanske."