Artikel top billede

HP har løst et af datalogiens største problemer

Et af matematikkens store, hidtil uløste problemer inden for kompleksitetsteori er nu muligvis løst af en forsker fra HP.

Computerworld News Service: Mens Hewlett-Packard forsøger at komme på benene igen efter koncernchef Mark Hurds pludselige fratræden på grund af anklager om sexchikane, kan virksomheden i det mindste være stolt af en enkelt potentielt imponerende præstation:

En forsker fra HP er stået frem med, hvad han mener, er en løsning af et af de sværeste, hidtil uløste problemer inden for datalogien.

Ledende forsker fra HP Labs,Vinay Deolalikar, har offentliggjort, hvad han hævder er en løsning af et matematisk problem, der er kendt som P versus NP.

Det har hidtil været regnet for et så svært problem at løse, at amerikanske Clay Mathematics Institute har udlovet en præmie på en million dollar - knap 5,7 millioner kroner i dagens kurs - til den person, der løser det.

Syv store problemer

Det er et af kun syv problemer, der er samlet under overskriften Millennium Prize Problems, og som instituttet har udlovet denne præmie for at løse.

Et af de syv, Poincaré-formodningen, blev officielt løst i 2006.

Det er endnu ikke afgjort, om Deolalikar vil få udbetalt kontantpræmien, da Clay Mathematics Institute endnu ikke har udtalt, om instituttet anser problemet som løst.

Dette problem, der er "et af de uafklarede problemer i datalogien," indebærer, at man skal "afgøre om der eksisterer spørgsmål, hvis svar hurtigt kan efterprøves, men som kræver umuligt lang tid at løse med nogen direkte fremgangsmåde," forklares det på instituttets website.

I det matematiske problem står P for polynomial tid og NP står for nondeterministisk polynomial tid.

"Det glæder mig at kunne bekendtgøre et bevis på, at P ikke er lig med NP," skriver Deolalikar i en e-mail til en gruppe matematik-professorer.

Denne e-mail blev i søndags offentliggjort på en blog af Greb Baker, der underviser ved British Columbia Simon Fraser Universitetet.

Dette vil løsningen komme til at betyde

Dette betyder i en nøddeskal, at visse problemer kun kan løses ved brute force-metode, hvis der overhovedet kan findes en løsning.

"Beviset kræver en sammenkobling af principper fra forskellige områder af matematikken. Den største udfordring ved konstruktionen af dette bevis var at afdække en kæde af konceptuelle forbindelser mellem forskellige felter og undersøge dem i et fælles perspektiv," skriver Deolalikar.

Folk med viden om problemet tøver helt naturligt med at erklære problemet løst af Deolalikar, da der først skal foretages en stor del efterprøvning.

Og selvom Deolalikar bliver rost for sin grundige tilgang, der adskiller sig fra de mere uorganiserede forsøg, der oftest præsenteres, så er der endnu ingen, der definitivt har hævdet, at han har løst problemet.

"Beviset synes at introducere nogle tankevækkende nye ideer, særligt en forbindelse mellem statistisk fysik og karakteristikken af NP i førsteordens prædikatslogik," skriver Scott Aaronson, der er adjunkt i elektroteknik og datalogi ved Massachusetts Institute of Technology, i et forbeholdent blogindlæg.

"Jeg ved ikke, hvad jeg skal mene lige nu, men jeg er bestemt håbefuld," skriver Dick Lipton, der er professor i datalogi ved Georgia Institute of Technology.

Oversat af Thomas Bøndergaard




Brancheguiden
Brancheguide logo
Opdateres dagligt:
Den største og
mest komplette
oversigt
over danske
it-virksomheder
Hvad kan de? Hvor store er de? Hvor bor de?
Ciklum ApS
Offshore software- og systemudvikling.

Nøgletal og mere info om virksomheden
Skal din virksomhed med i Guiden? Klik her

Kommende events
Styrk din virksomhed med relevant, pålidelig og ansvarlig AI integration med SAP

Kom og få indsigt i, hvordan du bruger AI til at transformere og effektivisere dine arbejdsgange. Vi kigger nærmere på AI-assistenten Joule, der vil revolutionere måden, brugerne interagere med SAP’s forretningssystemer. Og så får du konkret viden om, hvordan du kommer i gang med at bruge AI til at booste din forretningsudvikling.

03. december 2024 | Læs mere


Fyr op under vækst med dataanalyse, AI og innovation

Hvor langt er den datadrevne virksomhed nået i praksis? Det kan du høre om fra virksomheder, som har foretaget transformationen. Du kommer også til at høre, hvordan de anvender AI i processen, hvilke mål de har nået, hvordan de har høstet gevinsterne og hvilke nyskabelser, der er på vej i horisonten.

04. december 2024 | Læs mere


Vejen til skyen

Få indsigt i, hvordan overgangen til en samlet cloud-platform har styrket virksomhedens agilitet, fjernet datasiloer og leveret realtidsdata for bedre beslutningstagning.

04. december 2024 | Læs mere