Indisk matematiker får på puklen for at sige P er ikke lig NP

Eller formuleret på en anden måde: Svære matematiske problemer vil aldrig kunne løses ad simpel vej uden at have held i sprøjten. Hvis beviset er sandt (hvilket det dog ikke tyder på), er det godt nyt for kryptografer og computernes sikkerhed.

Læs hele artiklen med kommentarer på ing.dk

Matematikere og dataloger verden over har i disse dage noget at snakke om. Det største og mest berømte uløste problem inden for den teoretiske datalogi er påstået løst af Vinay Deolalikar fra HP Labs i Californien. I et 103 sider langt bevis, nu lagt online på scribd, skriver Deolalikar, at han har vist, at P ikke er lig NP - en efterhånden ikonisk ligning, der kort fortalt går ud på, at der findes fundamentale og uovervindelige forskelle i sværhedsgraden af matematiske problemer.

Hvis Deolalikars bevis er korrekt, venter der en check på en million dollar fra Clay Mathematics Institute, idet spørgsmålet om P=NP er en af resterende seks Millennium Prize-opgaver, som matematikere verden over ønsker at se løst. Men siden beviset blev offentliggjort 6. august, har en række førende matematikere allerede fundet flere huller og uklarheder. Ikke desto mindre mener man, at beviset indeholder tilpas mange nye ideer og perspektiver til, at det fortjener at blive diskuteret, selv om det er forkert.

P-problemer
Spørgsmålet om P=NP eller ej, har både fundamentale filosofiske og helt konkrete implikationer for computer- og kompleksitetsforskningen. Men hvad betyder P og NP egentlig?



I 1960'erne begyndte dataloger at ordne matematiske problemer i forhold til, hvor mange operationer eller antal regnetrin, der skal til for at løse dem. De så f.eks., at regnestykket 12x2 er lettere at løse end 12^2, fordi en fordobling af et vilkårligt tal med k cifre kræver, at man ganger hvert enkelt ciffer med to, hvorimod en kvadrering normalt kræver, at man ganger hvert ciffer med hvert ciffer. Antallet af regnetrin for en fordobling er altså ligefrem proportional med k, hvorimod antallet af regnetrin for en kvadrering er proportional med k^2.

Endnu sværere regnestykker kræver k^3 eller k^4 trin, hvilket svarer til en polynomiel stigning i antallet af regneoperationer på en computer. De fleste normale regnestykker fra gymnasiet er af den beskaffenhed, og matematikerne siger, at de er 'af polynomiel art' eller 'af typen P'.

NP-problemer
Men der findes også problemer, som er meget sværere at løse, for eksempel opgaven 'find et tal som går op i 1.050.504.368.559.379, og det må ikke være tallet 1 eller tallet selv'. Hvis man vil prøve lykken, må man regne med oddset én ud af 30 millioner, hvilket er en del sværere end at vinde i lotto. Det skyldes, at 1.050.504.368.559.379 kun er et produkt af to tal, nemlig primtallene 18.712.789 og 56.138.311, altså tal, som kun kan deles med sig selv og 1.

Der findes ingen deterministiske metoder, hvormed man konsistent kan løse den slags NP-opgaver hurtigt, end ikke på computere, og gudskelov for det, for krypteringsteknikkernes sikkerhed på bl.a. internettet afhænger af det. Man kalder denne form for matematiske problemer for NP-problemer, hvilket står for 'nondeterministic polynomial'. Det skyldes, at man endnu ikke har fundet nogen effektiv deterministisk metode, hvormed man kan løse dem på samme måde, som man kan løse problemer af typen P. Man kan gætte og være heldig - eller få et surt arbejde.

Men ikke desto mindre er de meget vigtige for en række praktiske problemer: Hvordan finder man den optimale måde, hvormed industrimaskiner kan operere på et givent område? Hvordan koordineres hjemmeservice bedst? Hvordan løser man et vanskeligt puslespil? Eller en sudoku? Eller her den klassiske: Hvordan bruger en handelsrejsende mindst muligt benzin, hvis han pendler mellem k forskellige byer? Alle disse problemer er NP-problemer, men måske er de i virkeligheden blot problemer af typen P, hvor vi bare endnu ikke kender beregningsmetoden?

Ingen grænseløs erkendelse
Afgørende i denne sammenhæng er, at mange NP-problemer er såkaldt 'NP-komplette', hvilket betyder, at hvis man først har vist, at ét NP-komplet problem (som f.eks. den handelsrejsende) er af typen P, så er alle andre NP-problemer det også. Selv om der findes et utal af NP-komplette problemer, har man ikke fundet nogen effektiv løsningsformel for en eneste af dem.

Deolalikar mener at kende svaret, og svaret er at det vil man aldrig kunne. P er ikke lig NP. Man kan altså ikke reducere NP-problemer til P-problemer. Hans bevis, hvis rigtigt, betyder, at selv om der findes simple løsninger til svære gåder, kan de end ikke principielt findes ad rationel vej. Vi kan kun håbe på held og kreativitet. Ligesom det var tilfældet med Gödels ufuldstændighedsteorem, vil den stadig udbredte tro på, at den matematisk-naturvidenskabelige metode besidder nøglen til grænseløse erkendelse, endnu engang blive gendrevet.

Kritikken er hård
Deolalikar sendte sit paper rundt blandt kolleger, inden det var gået igennem peer review, hvilket er ved at blive almindelig praksis, hvis man ønsker at få hurtig feedback. Og den er bestemt ikke udeblevet. I løbet af de sidste uger har hundreder af matematikere og dataloger diskuteret beviset på blogs og via e-mail. Meget af trafikken er gået igennem Georgia Tech-datalogen Richard Liptons blog. Tidligere professor i kvanteinformation ved University of Queensland Michel Nielsen har lavet en wiki, som forsøger at samle argumenterne fra de mange tråde og underdiscipliner.

Flere matematikere mener nu, at der er alt for store mangler. Især støder det, at beviset ikke virker for matematiske problemer, som er i sværere kompleksitetsklasser kaldet 2SAT eller XOR-SAT, selv om man ved at, der findes algoritmer for dem, som kan løses i polynomial tid.

Også Neil Immerman fra University of Massachusetts siger i en e-mail, at han har fundet en alvorlig fejl i Deolalikars paper.

Deolalikar forsøger at bevise, at nogle problemer er i NP-klassen uden at være i P-klassen ved at bruge en anden matematisk klasse kaldet FO(LFP). Men ifølge Immerman kan denne klasse ikke bruges på den måde, fordi man så ikke vil kunne dække alle P.

Scott Aaronson fra MIT mener, at der er mindst otte tegn på, at beviset er forkert, og han har endda satset sine egne sparepenge på det:

»Hvis Vinay Deolalikar modtager den en million dollar doterede Clay Millenium Prize for sit bevis på, at P ikke er lig NP, vil jeg, Scott Aaronson, personligt supplere prisen med 200.000 dollar,« skriver han på sin blog.

Terence Tao fra UCLA mener dog, at Deolalikars overordnede strategi endnu ikke har vist sig at være helt håbløs:

Selv om det viser sig, at man ikke kan redde beviset, selv med store reparationer, så er det stadig tænkeligt, at selve strategien er god nok.

Under alle omstændigheder viser debatten, at frontforskning kan gøres på en anden og mere spændende måde end fagblade og lange forelæsninger - nemlig via debatfora, blogs, wikis og et aktivt og åbent forskningsmiljø på internettet.

0 comments:

There was an error in this gadget