65-årig matematiker laver gennembrud i kompleksitetsteorien

Var du stærk til grafisomorfi i skolen? Hvis ikke, så er det ikke noget at være flov over, for grafisomorfi hører til en gren af matematikken kaldet ‘kompleksitetsteori’, og det står bestemt ikke på de flestes skoleskema.

Nu har den 65-årige ungarske matematiker László Babai tilsyneladende fået et gennembrud inden for grafisomorfi, der har vakt stort postyr blandt de teoretiske matematikere i hele verden.

Hvis den modne matematikers beregninger holder stik, har han opdaget en langt mere effektiv måde at vurdere, om to grafer, der ser helt forskellige ud, i virkeligheden er ens.

Det indikerer samtidig, at grafisomorfi faktisk er en langt mindre kompleks disciplin, end matematikerne hidtil har troet.

»Det er ét af de mest kendte problemer, man har arbejdet på i kompleksitetsteori, og det har vist sig at være meget svært. Hvert et lille fremskridt har man opfattet som et stort skridt, så det her er helt klart et kæmpe gennembrud,« siger Kristoffer Arnsfelt Hansen, der er lektor på Institut for Datalogi på Aarhus Universitet og forsker i kompleksitetsteori.

Du kan, hvis du tør, se László Babai præsentere sit arbejde til et foredrag længere nede i artiklen.

Grafer kortægger dine Facebook-venner

Ved grafisomorfi undersøger matematikerne overordnet set, om alle knudepunkterne i to tilsyneladende forskellige netværk, i virkeligheden er forbundet på samme måde – og dermed altså, om de to netværk i virkeligheden er det samme.

En graf ligner i denne forbindelse ikke en ‘almindelig’ graf med en x-akse og en y-akse, men viser i stedet et netværk med punkter og deres forbindelser, kaldet kanter (se illustrationen længere nede på siden).

»Det kunne for eksempel være Facebook-grafen, der består af brugere, og så er der en vennerelation imellem dem. Det er nogle knuder, kalder man dem, og så har de kanter imellem sig,« fortæller Kristoffer Arnsfelt Hansen.

Et andet eksempel er en såkaldt ‘molekylegraf’, hvor atomerne er knuderne i grafen, og de kemiske bindinger er kanterne. Ved at bestemme deres grafisomorfi, kan forskerne skelne molekylerne fra hinanden og lave databaser over molekyler.

Nogle gange kan man genfinde to grafer forskellige steder, men hver især kan de være så filtrede, at det ikke umiddelbart er til at se, om de i virkeligheden er ens.

»Problemet er, at man ikke ved, hvilke knuder, der svarer til hvilke knuder. De kommer helt uordnet. Man kunne også forstille sig, at man havde tegnet dem på papir, og så kunne de her knuder ligge på vilkårlige måder, og så er det simpelthen ikke muligt bare at se, hvordan strukturen er,« forklarer Kristoffer Arnsfelt Hansen.

Kompleksiteten vokser som en eksplosion

Jo flere knudepunkter, der er i to grafer, des mere komplekse kan de være, og des længere tid skal en computer bruge på at finde ud af, om de er ens.

Men der kan være stor forskel på, hvor indviklede beregningerne bliver, efterhånden som inputlængden til computeren vokser. Nogle problemer, kaldet ‘P’-problemer, vokser relativ langsomt i kompleksitet. Matematikerne siger, at deres ‘køretid’ – den tid, en computer skal bruge på at løse dem – vokser i ‘polynomiel tid’.

Her kan du høre med til foredraget, hvor Lázsló Babai præsenterer sit matematiske gennembrud. Advarsel: Ikke for almindelige dødelige. (Video: University of Chicago)

Men der er også en langt vanskeligere klasse af problemer, kaldet ’NP-hårde’ problemer. NP-hårde problemer bliver også mere indviklede, jo større input computeren skal regne på, men de bliver også langt hurtigere komplekse. For disse problemer mener matematikerne, at de kræver ‘eksponentiel tid’ for at kunne løses.

»For eksponentiel tid vil der ligesom være en hård opbremsning. Man når en inputstørrelse, og lige meget om man forbedrer computeren 10 gange, så vil man ikke kunne håndtere signifikant større input. Eksponentiel tid er ligesom en eksplosion, så det er ikke særlig rart med sådan nogle algoritmer,« forklarer Kristoffer Arnsfelt Hansen.

Måske et langt lettere problem

Selvom moderne computeralgoritmer løser grafisomorfi-problemerne i eksponentiel tid, kan László Babais nye algoritme – næsten – løse problemerne i polynomiel tid.

Det betyder, at grafisomorfiske problemer nu ser mere ud til at være et af de lettere P-problemer end de vanskeligere NP-hårde problemer.

»Umiddelbart må man klart forvente, at det peger imod, at det falder i klassen P. Måske er det bare et spørgsmål om tid fra nu af, før man finder en polynomiel tidsalgoritme. Men selv det kan tage lang tid,« forklarer Kristoffer Arnsfelt Hansen.

László Babais algoritme er fuldstændig teoretisk, og den hjælper ikke umiddelbart med at løse praktiske problemer, fortæller den danske lektor.

Det skyldes for det første, at de eksisterende algoritmer allerede er så gode, at de kan løse grafisomorfiproblemer meget hurtigt.

Og for det andet, er det meget vanskeligt for matematikerne overhovedet at finde grafisomorfiproblemer, som tager lang tid at løse for en computer.

»Så til praktiske formål kan man sige, at problemet er løst,« bemærker Kristoffer Arnsfelt Hansen med henvisning til, at moderne computere i forvejen kan knække grafisomorfi-problemer temmelig hurtigt.

Problemet passer måske ikke i kasserne

Til gengæld har gennembruddet betydning for, hvordan matematikerne opfatter hele grafisomorfi-problemet, som indtil videre ikke med sikkerhed passer ind i hverken klassen af P-problemer eller NP-hårde problemer.

Et lignende problem, der heller ikke passer ind i sådan en kasse, er faktorisering af hele tal, som kryptografi og sikkerhed på internettet er baseret på.

Alt tyder på, at faktorisering af hele tal ikke hører til i klassen af P-problemer, selvom det heller ikke er blevet klassificeret som et af de NP-hårde problemer.

Men i princippet kunne faktorisering af hele tal en dag vise sig at være et af de sårbare P-problemer, og det ville have en ødelæggende effekt på sikkerheden på internettet.

Og begge problematikker prikker til en endnu dybere problemstilling i matematikken, som spørger, om der i virkeligheden findes en tredje, ukendt type af beregningsproblemer.

»Altså, findes der nogle naturlige ting, som ikke passer ned i de kasser eller ej?« spørger Kristoffer Arnsfelt Hansen.

Han er ikke typen, der laver fejl

László Babai har præsenteret sit nye arbejde igennem en række foredrag på University of Chicago, men han vil ikke udtale sig til medierne, før resultaterne er blevet publiceret i et videnskabeligt tidsskrift.

»Jeg forstår godt, at i internettets tidsalder, kan selv en simpel udmelding under et seminar udløse en eksplosion i blogosfæren (bloggernes fællesskab på internettet, red.), men det er ikke nogen grund til at sætte processen over styr,« sagde László Babai til New Scientist.

Kristoffer Arnsfelt Hansen har dog stor tillid til den ungarske matematikers evner.

»Der er ikke noget peer-review, men jeg tror altså, at han ikke lige er typen, der laver fejl. Han er fuldstændig sikker på, at det er rigtigt, ellers ville han ikke offentliggøre det på den måde,« siger Kristoffer Arnsfelt Hansen.

Han udtrykker samtidig stor beundring over Lázsló Babais klare fokus, hvor han hårdnakket har arbejdet videre med problemerne, selvom de tog mange år at løse.

»Han er 65 år. Han har arbejdet på det her problem, eller lignende problemer hele sin karriere, og man kan sige, at det er måske kun ham, der kan gøre det og har den indsigt,« siger Kristoffer Arnsfelt Hansen.