23/08-11 - Pressemeddelelse

Datalogiens uløste problemer får nu kamp til stregen

COLA, enhver datalogs basale livskilde, er nu også navnet på et projekt, der har ambitioner om at løse et af datalogiens million-dollar-spørgsmål.

Lektor Jakob Grue Simonsen fra DIKU har modtaget en bevilling på 6,9 mio. kr. fra Det Frie Forskningsråds Sapere Aude-forskerkarriereprogram til et projekt, der over de næste 4 år skal udforske løsninger på et af datalogiens helt store fundamentale spørgsmål. "Kan det bevises, at P = NP eller ej? Eller hvorfor kan man ikke bare løse ethvert komplekst problem med en algoritme og en supercomputer?"

COLA står for Complexity via Logic and Algebra og er et rent grundforskningsprojekt, som med hjælp fra nogle af verdens bedste forskere inden for logik, matematik og datalogi skal udforske nye teoretiske tilgange til et af datalogiens væsentligste uløste problemer. Målet er i første omgang ikke en løsning på problemerne, men udvikling af nye matematiske værktøjer, som kan bruges til at løse dem.

Drømmen om at løse en af universets store gåder: P = NP
"Det er en af mine drengedrømme, der nu går i opfyldelse" siger Jakob Grue Simonsen. "De store åbne spørgsmål har altid fascineret mig. Er det overhovedet muligt at angribe nogle af de problemer, der har voldt mine forskerkolleger kvaler gennem mere end 40 år? Vi vil i hvert fald forsøge."

Med et hold af 2 post-docs, 2 ph.d.-er og en række førende internationale gæsteforskere vil COLA søge helt nye tilgange til løsning af et problem, der i fagsprog omtales som P versus NP-problematikken. Løst sagt står P for klassen af problemer, der har "effektive" løsninger, NP står for klassen af problemer, hvor det er let at tjekke, at et bud på en løsning faktisk er en løsning. Men at få de to ender til at mødes ved hjælp af programmering og algoritmer er endnu ikke lykkedes.

P = NP-spørgsmålet har udfordret verdens forskere i den grad, at det er blevet udnævnt som et af årtusindskiftets store videnskabelige udfordringer, og det amerikanske Clay Mathematics Institute har sat 1 million dollars på højkant til den, der formår at løse problemet.

Problemet belyst ved et eksempel
Skemalægning er en årligt tilbagevendende prøvelse for skoleledere. Man har et antal elever, et antal klasser, et antal rum, et antal lærere og et antal fag - og disse elementer skal gå op i en højere enhed i et sindrigt puslespil, som til sidst munder ud i et fælles skema for hele skolen med den optimale ressourceudnyttelse, dvs. ingen mellemtimer, ingen aftenundervisning, ingen uheldige klassesammensætninger og ingen dobbeltbooking af fysiklokalet.

Det lyder umiddelbart som en banal opgave at få en computer til at regne den bedste løsning ud. Men faktum er, at så snart der kommer flere end nogle ganske få komponenter til, vil det tage uoverkommelig lang tid for computeren at regne sig frem til den optimale løsning. Visse optimeringsproblemer er så komplicerede, at selv om man havde alle jordens supercomputere til rådighed, ville problemet ikke kunne løses inden for en menneskelig tidsramme. Forskere verden over har siden datalogiens barndom i 60'erne kæmpet med at finde en formel til at løse denne gordiske knude, fordi den principielt ville give løsninger til de fleste optimeringsproblemer, som findes i praksis.

Om det lykkes at nå frem til et svar på, om P = NP?, må tiden vise. Men som output af projektet skal der under alle omstændigheder bygges fundamentale matematiske værktøjer, der kan hjælpe med at forstå grænserne for effektive beregninger, uanset om sådanne beregninger foretages af computere bygget af mennesker, af andre intelligensvæsener eller computeren selv gennem maskinlæring.

"Den kommende tid vil gå med at rekruttere forskere til projektet" fortæller Jakob videre. "Hvordan det kommer til at forløbe er i sagens natur svært at forudse. Strategien er at forfølge forskellige veje til målet, nemlig dels en der bygger på hidtil kendte metoder og resultater, der så angribes fra forskellige vinkler, dels nogle mere dristige tilgange, der gør op med hidtil kendte metoder."

Om Jakob Grue Simonsen
Jakob Grue Simonsen er lektor ved Datalogisk Institut Københavns Universitet og tilknyttet Forskergruppen Human Centered Computing. Jakob forsker i matematisk beskrivelse af beregnelighed og kompleksitet, særligt i forbindelse med beregninger med uendelige strukturer. Aktuelt er han involveret i projekterne 'Udvikling af programmeringssprog til beregninger i computere på molekyleskala', 'Anvendelse af maskinlæring og processering af naturligt sprog til karakterisering af brugeres opfattelse af brugbarhed af software' samt 'Wallviz, visualisering af store mængder programtekst og afviklingen af samme på storskærme'.

COLA-gruppen vil blive etableret på KUs Søndre Campus på Amager. Sapere Aude-bevillingen løber fra april 2012 til marts 2016.