Information 24 januar 2000, 1 . sektion side 6

P=NP?

Eller spurgt på en anden måde: Kan nye matematiske indsigter opnås uden at have held i sprøjten?

Matematik
Af Robin Engelhardt

Bag ovenstående kryptiske overskrift gemmer der sig et af tidens mest interessante matematiske og filosofiske problemer. Faktisk handler det om en problemstilling, som beskæftiger sig med de mest fundamentale grænser for den menneskelige erkendelse. Intet mindre. Populærvidenskaben har for længst indoptaget kaosteori og katastrofeteori. Men det her er en stjerne på vej. Måske ser »P=NP?« ikke ud af så meget, men det har afgørende betydning for utrolig mange ting.

Hvad er P?
Historien starter i 1960 erne. Her begyndte de første matematikere at spekulere over måder, hvorpå man kan ordne matematiske problemer i forhold til deres sværhedsgrad. Men hvordan definere »sværhedsgrad«? Forskerne enedes om at lade sværhedsgraden angive antallet af operationer ­ eller regnetrin ­ man skal bruge for at komme frem til en løsning af et givent matematisk spørgsmål. Man kunne for eksempel spørge, om tallet 12x2 er nemmere at beregne end tallet 122, det vil sige om disse to forskellige regnestykker har forskellige sværhedsgrader. I dag ved man, at det at kvadrere er sværere end at fordoble. En fordobling af et vilkårligt tal med k cifre kræver, at man ganger hvert enkelt af de k cifre med to. Dvs. antallet af regneskridt er ligefrem proportional med k. En kvadrering derimod kræver normalt, at man ganger hvert ciffer med hvert ciffer, og dermed kommer op på k2 operationer (for slet ikke at nævne summationen bagefter). Men der findes også endnu sværere regnestykker, som kræver k3 eller k4 operationer, og jo sværere de bliver, jo længere tid vil det tage at beregne på en computer. De fleste problemer, man kender fra skolen, er af præcis den beskaffenhed: Man kan beregne dem ved hjælp af kr trin, hvor r er et naturligt tal og k antal af cifre på det tal, man begyndte med. Lægge sammen, gange, dividere, finde rødder, løse ligninger osv. ­ alle kan de løses med maksimalt kr operationer (for forskellige værdier af r, vel at mærke). Og i de tilfælde siger man, at de er af »polynomiel art« eller af »typen P«. Det er, hvad det første bogstav i overskriften betyder.
Faktisk findes der matematiske problemer af typen P, som stadig tiltrækker forskernes interesse. Blandt andet sorteringsalgoritmer. Alle kender det møjsommelige arbejde i at sortere adresselister eller spillekort eller lignende efter en bestemt rangorden. Normalt ville man starte med f.eks. at lede efter den adresse i listen (med k adresser), som starter højest oppe i alfabetet. Til det kræves maksimalt k operationer, idet det jo ikke er sikkert, at man kan finde den rette adresse med det samme. Med den næste adresse kræves der maksimalt k-1 operationer, den næste igen k-2, osv.. Det vil sige, at man kan komme op på 1+2+3+...+k=k(k+1)/2 operationer, og da det tal kan sammenlignes med k2 for store k, er sorteringsalgoritmen af typen k2. Men sjovt nok kan man gøre det meget hurtigere og få eksponenten helt ned i nærheden af r=1 takket være kloge hoveder og fiffige programmører.

Hvad er NP?
Men der findes også problemer, som er meget mere krævende end dem af typen P. 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 metoder, hvormed man konsistent kan løse den slags opgaver hurtigt, end ikke på computere, og gudskelov for det, fordi 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 kunne løse dem på samme måde, som man kan løse problemer af typen P. Man kan kun gætte og være heldig eller også få et rigtigt 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? Eller her den klassiske: Hvordan bruger en handelsrejsende mindst mulig 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 kender svaret.

NP-komplet?
Nu begynder overskriften »P=NP?« måske langsomt at give mening. Det stiller spørgsmålet, om der findes NP-problemer, som kan reduceres til P, og som derfor kan løses uden brug af held. 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å. Hvis et problem er løst, så er alle de andre det også! Det skyldes, at alle den slags matematiske problemer af klassen NP kan omskrives til en kombination af logiske operatorer (som AND, OR, NOT, osv.), og på den måde generaliseres til de såkaldte Cook'ske problemer ­ opkaldt efter matematikeren Stephen Cook, der fandt på metoden i 1971. Hvis et NP-komplet problem kan vises at være af typen P, så betyder det, at tilfældighed alligevel er undværlig i matematikken ­ determinismens hellige grav er vel forvaret, og den eneste hindring for, at vi mennesker kan løse verdens værste matematiske gåder, er vores stadig inferiøre intellekt. Men det omvendte spørgsmål er mindst lige så interessant: Findes der NP-komplette problemer som garanteret ikke er af typen P? I så tilfælde vil de filosofiske implikationer være mindst lige så betydningsfulde. Så vil vi endelig vide, at selvom 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å heldet. Fremtidens naturvidenskabelige ikon vil ikke længere være nødvendighed men tilfældighed, og troen på den grænseløse erkendelse vil gå tabt. Men endnu er der ingen, som hverken har bevist det ene eller det andet. Selvom der findes et utal af NP-komplette problemer, har man ikke fundet nogen effektiv løsningsformel for en eneste af dem. Måske minder situationen lidt om situationen før Gödels berømte bevis om umuligheden i at finde et fyldestgørende og samtidig logisk konsistent grundlag for matematikken. Og måske vil man aldrig kende svaret på overskriften.

DNA-computere
Måske er der alligevel lys i horisonten. Man er nemlig begyndt at kigge på, hvordan naturen løser disse problemer. Der er dukket en hel forskningsgren op, der beskæftiger sig med de såkaldte »DNA-computere«. I 1994 kunne Leonard Adleman fra University of Southern California som den første finde en løsning på et NP-komplet problem ved hjælp af en DNA-computer, og nu, i det forrige nummer af fagbladet Nature, kunne Lloyd Smith fra University of Wisconsin løse et andet NP-komplet problem (det såkaldte »satisfiability problem« eller SAT). Metoden går ud på at repræsentere alle mulige løsninger til problemet i form af DNA-stumper (som jo er en slags logiske enheder, hvor baserne pares efter bestemte regler), sætte dem fast på en guldplade, og så lade de komplementære DNA-strenge, der tilfredsstiller nogle logiske delløsninger af problemet, flyde frit omkring. Efter at strengene har kombineret sig og dannet dobbeltstrenge, skylles nogle skræddersyede enzymer hen over guldpladen og eliminerer alle de DNA-strenge, som ikke er blevet bundet. Så fremdeles gentages proceduren i flere omgange. Til sidst er kun de DNA-dobbeltstrenge tilbage, som repræsenterer løsningen til hele problemet.
Fordelen ved denne form for »beregning« er, at den foregår parallelt: Alle forkerte løsninger fjernes samtidigt, og hastigheden, hvormed man finder løsningen, øges betragteligt. »I løbet af de næste fem år,« spår Smith, »vil vi se en enorm vækst på området.« Hvis DNA-computere i en ikke så fjern fremtid vil blive praktisk anvendelige, vil det skubbe grænsen for det beregnelige betydeligt. Men den prinicipielle sag om P=NP? er dog ikke løst af den grund.


Tilbage til indholdsfortegnelsen