Forskere vil kaste lys over et af verdens største matematikmysterier

I år 2000 udloddede det amerikanske Clay Mathematic Institute en dusør på en million dollars til de personer, der løser et af verdens syv største matematikmysterier. En million per løst mysterium vel at mærke. 

Seks af mysterierne er i dag, snart 20 år efter, stadig uløste.

I sit nye forskningsprojekt Beyond Satisfaction: Towards an Understanding of Real-World Efficient Computation skal lektor på Datalogisk Institut på Københavns Universitet Jakob Nordström skabe ny indsigt i et af de seks matematikmysterier.

Nemlig P vs. NP-problemet, som går ud på at finde ud af, om der for alle problemer, hvis løsning kan verificeres af en algoritme, også findes en algoritme, som kan finde løsningen.

- I dag er computere allevegne, og de har stor indflydelse på vores hverdag. På samme måde som partikelfysikere, der forsøger at forstå massens oprindelse, som er grundlaget for vores eksistens, forsøger vi at forstå computere og de processer i computere, som påvirker os overalt i vores hverdag i dag, siger Jakob Nordström.

Den handelsrejsendes problem
Som eksempel på P vs. NP-problemet, nævner Jakob Nordström den handelsrejsendes problem.

- Hvis du er handelsrejsende med et bestemt budget og et bestemt antal destinationer, du skal besøge for at sælge dine produkter, og du vil gøre det ad den kortest mulige vej, så har vi i dag ingen effektiv algoritme, som kan finde den bedste vej, siger Jakob Nordström.

Mængden af kombinationsmuligheder på en rejse stiger eksponentielt med mængden af stop på rejsen.

Når man når op på 1000 stop vil antallet af kombinationsmuligheder være så stort, at en standard lommeregner ikke en gang vil kunne udregne mængden af kombinationer.

Og hvis vi øger antallet af destinationer med en faktor 10 til 10.000, så bliver mængden af mulige kombinationer helt uoverskuelig.

Selv hvis man forestillede sig, at alle atomer i det kendte univers var en moderne supercomputer, som havde regnet på at finde den bedste rute siden big bang for cirka 13,8 milliarder år siden, så ville de stadig ikke være i nærheden af at have fundet løsningen. 

Problemet med den handelsrejsende kan skrives som en logisk formel, og det er faktisk logiske formler, Jakob Nordström skal regne på i sit projekt.

Eller rettere om der kan udvikles algoritmer til at løse logiske formler med mange kombinationsmuligheder, og hvor i udregningen algoritmen kommer til kort, når det ikke lykkes.

Forskningsprojektet er et grundforskningsprojekt, hvor forskerne både vil udvikle nye metoder til at udforske P vs. NP-problemet og langt bedre algoritmer end dem, der findes i dag.

Den type algoritmer vil for eksempel kunne bruges til hurtigere at kortlægge proteiner, når man vil udvikle ny medicin.

Forskningsprojektet er finansieret af Danmarks Frie Forskningsfond.