Datalogiens største problem måske løst

Det såkaldte P versus NP-problem har i mange år været betragtet som et af de ubestridt vigtigste spørgsmål inden for teoretisk datalogi. Kort sagt går problemet ud på enten at bevise eller modbevise, at svar, der er lette at verificere, også er lette at beregne.

Et utal af forhold inden for anvendt datalogi – herunder moderne kryptografi, der bl.a. er fundamentet for sikre transaktioner inden for finanssektoren, forsvaret og mange andre kritiske funktioner i samfundet – bygger på en forudsætning af at svar, der er lette at verificere, ikke nødvendigvis er lette at beregne; inden for datalogi udtrykt ved udsagnet: P ≠ NP.

Men hidtil har denne vigtige forudsætning altså kun været en antagelse, hvilket bl.a. fik det amerikanske Clay Mathematics Institute til i år 2000 at udlove en dusør på 1 million dollars til den, som formår at opstille et korrekt matematisk bevis for, om P er lig med NP eller ej.

Nu kan det længerestående problem imidlertid vise sig at være løst, da en anerkendt forsker hos HP Labs, Vinay Deolalikar, i sidste uge begyndte at cirkulere, hvad han hævder er et bevis for, at P ≠ NP. Beviset er meget kompliceret og inddrager ifølge forskeren selv idéer fra både logik, statistik, grafteori og statistisk fysik, og vurderinger af bevisets korrekthed fra andre forskere er derfor endnu meget begrænsede.

En professor i datalogi hos MIT skriver dog på sin blog:

http://www.technologyreview.com/blog/post.aspx?bid=349&bpid=25584 skrev:

What’s obvious from even a superficial reading is that Deolalikar’s manuscript is well-written, and that it discusses the history, background, and difficulties of the P vs. NP question in a competent way. More importantly (and in contrast to 98% of claimed P≠NP proofs), even if this attempt fails, it seems to introduce some thought-provoking new ideas, particularly a connection between statistical physics and the first-order logic characterization of NP. I’ll leave it to the commenters to debate whether Deolalikar’s paper exhibits one or more of the Ten Signs A Claimed Mathematical Breakthrough Is Wrong.

Beviset kan læses i sin helhed her.