Forsker-talent får 6,6 millioner til at påvise, at bestemte algoritmer ikke findes

Med fem mio. kr. fra Villum Fonden og 1,64 mio. kr. fra Aarhus Universitets Forskningsfond kan forsker Kasper Green Larsen fra Aarhus Universitet sammensætte en gruppe, der skal forsøge at knække nødden i, hvor hurtigt man kan søge, regne og analysere på enorme datamængder.

Projektet handler egentlig om klassiske problemstillinger som teoretiske dataloger har forsøgt at løse i over 40 år. Nogle af de vigtigste spørgsmål inden for datalogi handler om, hvorvidt konkrete beregningsproblemer kan løses mere effektivt (hurtigt) af en computer eller ej. Man taler om, at der må findes en nedre grænse for, hvor meget arbejde computeren skal udføre for at løse et beregningsproblem.

Forskningsgruppen, der med bevillingerne bliver udvidet med to ph.d.’ere og en post.doc, skal udvikle matematiske metoder, der kan bevise at beregningsproblemer umuligt kan løses effektivt. Det kan spare både forskningsmidler og tid, der ellers ville være spildt i forsøg på at udvikle løsninger, der ikke findes.

“Der er masser af problemer, hvor det går for langsomt, fordi vi ikke har effektive algoritmer. Her er det selvfølgelig interessant at spørge om det overhovedet kan lade sig gøre. I projektets ene vil vi undersøge om det kan lade sig gøre at søge mere effektivt i databaser, og den anden del handler om, hvor hurtigt man kan regne og analysere på enorme datamængder,” siger Kasper Green Larsen, der er tilknyttet det datalogiske center MADALGO, der hører under Danmarks Grundforskningsfond ved Aarhus Universitet.

Kasper Green Larsen har tidligere gjort rent bord med sin forskning og har vundet det, der svarer til den teoretiske datalogis “Oscar”. Tilbage i 2012 vandt han to priser ved en af verdens højest rangerede konferencer inden for teoretisk datalogi, “ACM Symposium on Theory of Computing” - også kendt som STOC - for at vise, at dynamiske databaser ikke kan håndtere de enorme datamængder mere effektivt end de gør nu.

Området har for eksempel stor betydning inden for et nyt felt som bioinformatik, hvor man bruger dna-sekventering for at se om bestemt medicin virker godt på en tumor. Det menneskelige genom består at tre milliarder basepar og det kan en computer typisk kigge igennem på en halv time. Skal man derimod beregne afstanden og dermed forskellen mellem to menneskelige genomer, er man ude i et regnestykke på tre milliarder kvadrerede operationer. Det giver tallet ni efterfulgt af 18 nuller.  

Og ifølge Kasper Green Larsen troede mange forskere indtil for nylig, at det var muligt at løse det mere effektivt. Men forskere fra MIT påviste sidste år, at det beregningsmæssigt er umuligt, hvilket vil sige, at selv de bedste computere over lang tid ikke vil kunne generere et svar.

“Det er faktisk et reelt problem, fordi det skal selvfølgelig helst ikke tage computeren mere end en dag at regne ud, hvordan en tumor hos en kræftpatient er muteret. Budskabet med resultatet fra MIT er, at man aldrig kan lave en blackbox-løsning, der effektivt kan beregne forskellene mellem vilkårlige DNA-strenge. Derfor prøver man i praksis at udnytte at menneskelige genomer ligner hinanden rigtigt meget. Denne viden kan, og vi ved nu, at den også skal udnyttes for at gøre algoritmerne hurtigere,” siger Kasper Green Larsen.

Bevillingen er en del af en pulje på 119 millioner kr. som Villum Fonden uddeler til 20 unge forskere hvert år. Villum Fonden er en almennyttig fond, der støtter forskning, miljø og bæredygtighed samt kulturelle og sociale projekter.