Akademia.Zand.News – I år 2000 udloddede Clay Mathematic Institute en dusør på en million dollars til de personer, der løser blot et af verdens syv største matematikmysterier.
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. Det skriver Danmarks Frie Forskningsfond.
En million dollars for at løse et matematikmysterium
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 versus NP-problemet (også kaldet P=NP, red.), 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.
Problemet spørger om alle elementer i P-klassen, også kan findes i NP-klassen. P står for polynomiel tid og NP står for non-deterministisk polynomiel tid, som ofte er søgende algoritmer. (Kilde: Wikipedia).
»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 med kombinationsmuligheder
Som eksempel på P versus 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å 1.000 stop, vil antallet af kombinationsmuligheder være så stort, at en standard lommeregner ikke en gang vil kunne udregne mængden af kombinationer.
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.
Formålet er at udvikle algoritmer med mange kombinationer
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, som finansieres af Danmarks Frie Forskningsfond.
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 versus 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.
Øverst: Pressefoto. (Foto: Danmarks Frie Forskningsfond). PM/rk.
This article is published by Zand.News. Copyright © Zand Media, Denmark (EU), tel. +45 7174 1448.