Danmarks Frie Forskningsfond

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

Del

Matematik: Danske forskere skal skabe en større forståelse af et af de såkaldte Millennium Prize Problems. Grundforskningen kan være første skridt på vejen til at udvikle bedre algoritmer til at løse et væld af udfordringer.

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.

Nøgleord

Kontakter

Billeder

Information om Danmarks Frie Forskningsfond

Danmarks Frie Forskningsfond
Danmarks Frie Forskningsfond
Asylgade 7
5000 Odense C

https://dff.dk/

Følg pressemeddelelser fra Danmarks Frie Forskningsfond

Skriv dig op her, og modtag pressemeddelelser på e-mail. Indtast din e-mail, klik på abonner, og følg instruktionerne i den udsendte e-mail.

Flere pressemeddelelser fra Danmarks Frie Forskningsfond

35 fremragende Sapere Aude Forskningsledere skal forny forskningsfronten19.11.2019 09:04:52 CETPressemeddelelse

Dansk forskning beriges med forskning i international klasse. 35 excellente DFF: Sapere Aude Forskningsledere skal sætte en ny retning inden for et bredt felt af forskningsområder. - Danmarks Frie Forskningsfond har peget på de allerdygtigste, yngre forskere med vægt på banebrydende idéer og lederambitioner i top til gavn for Danmarks fremtid, siger bestyrelsesformand David Dreyer Lassen.

I vores nyhedsrum kan du læse alle vores pressemeddelelser, tilgå materiale i form af billeder og dokumenter samt finde vores kontaktoplysninger.

Besøg vores nyhedsrum