Datalogiens største problem: P versus NP

Der findes syv matematiske problemer, som blev udpeget som så svære og interessante, at Clay Mathematics Institute kaldte dem millenniumsproblemer, og for at løse hvert af dem får løseren en dusør på en million dollar. Et af problemerne berører også datalogien og hedder problemet P versus NP. Lad os forklare, hvad dette problem egentlig handler om.

Lad os bare sige det, som det er. Lad os ikke bilde os ind, at det bliver nemt at forklare. Det er trods alt et millenniumsproblem. Så lav dig en god kop grøn te 🍵, og lad os komme i gang. Først viser vi fire forskellige problemer fra datalogiens og algoritmernes verden. Vi analyserer problemerne og viser, hvordan de forholder sig til bogstaverne P og NP.

Problem nr. 1: Find det mindste tal

P vs. NP handler om algoritmer og deres kompleksitet. Forestil dig, at jeg hældte hundrede sedler ud foran dig, på hver af dem stod der ét tal, og at jeg ville bede dig finde den seddel, hvor det mindste tal står. Hvor lang tid vil det tage dig?

Et halvt minut? To minutter?

Det er tidsenheder, som ikke interesserer os så meget i den teoretiske datalogi. Det, der interesserer os, er snarere antallet af operationer. Vi kunne altså spørge lidt anderledes: hvor mange sedler skal jeg kontrollere for at være sikker på, at jeg har fundet det mindste tal? Svaret er, at jeg skal kontrollere alle sedlerne — for det mindste tal kan stå på den allersidste seddel. Når jeg kaster hundrede sedler foran dig, skal du kontrollere hundrede sedler. Når jeg kaster tusind sedler foran dig, skal du kontrollere tusind. Generelt gælder, at når jeg kaster n sedler foran dig, skal du kontrollere n sedler.

Det kalder vi algoritmers kompleksitet. Hvis jeg kaster n sedler foran dig, og du skal udføre n operationer for at finde det mindste tal, betyder det, at denne algoritme til at finde det mindste tal har kompleksiteten n, hvilket vi også kalder lineær kompleksitet, fordi kompleksiteten beskrives af en lineær funktion.

Okay, du har gennemgået hundrede sedler og meddelt, at det mindste tal er 17. Hvordan kan jeg kontrollere, at du taler sandt? Der findes ingen anden måde end igen at gennemgå alle sedlerne og kontrollere, at der ikke står et mindre tal på nogen af dem. Du skal altså se på n sedler for at finde det mindste tal, og når jeg vil kontrollere det, må jeg gøre det samme. Kompleksiteten af at kontrollere resultatet er altså også n, lineær kompleksitet.

Findes der algoritmer, hvor det er lettere at kontrollere resultatet end at finde det?

Problem nr. 2: Produktet af et par

Forestil dig, at jeg hælder to lige store bunker sedler ud foran dig, og på hver seddel står der igen ét tal. Og nu ville jeg bede dig finde et tal fra bunke A og et tal fra bunke B, så deres produkt giver tallet 918. Lad os for eksempel have disse bunker af tal:

$$\begin{array}{rcl}A& =& \{49,11,32,54,15\}\\ B& =& \{17,64,74,61,21\}\end{array}$$

Hvordan kan vi finde et talpar, så deres produkt er lig med 918? Vi kan simpelthen prøve alle muligheder. Hvor mange er der? Ret mange, der er 25. Vi begynder med at gange det første tal fra bunke A, altså tallet 49, med hvert tal fra bunke B:

$$\begin{array}{rcl}49\cdot 17& =& 833\\ 49\cdot 64& =& 3136\\ 49\cdot 74& =& 3626\\ 49\cdot 61& =& 2989\\ 49\cdot 21& =& 1029\end{array}$$

Intet talpar giver 918. Vi prøver derfor det samme med de resterende tal fra bunke A, altså yderligere fem par for tallet 11, yderligere fem par for tallet 32, yderligere fem par for 54 og de sidste fem par for 15. I alt kan vi prøve 25 talpar. Til sidst finder vi ud af, at 54 · 17 = 918.

Hvad er kompleksiteten af denne algoritme? Vi er interesserede i, hvor mange talpar vi måtte gange. Begge bunker indeholdt fem sedler, og vi måtte prøve hvert af de fem tal fra den første bunke sammen med hvert af de fem tal fra den anden bunke. I alt prøvede vi 5 · 5 = 25 kombinationer. Hvis jeg kastede to bunker med 10 sedler foran dig, skulle du prøve 10 · 10 = 100 kombinationer. Generelt gælder, at hvis jeg kaster to bunker med n sedler foran dig, skal du prøve n · n = n² kombinationer.

Vi siger, at denne vores algoritme har kompleksiteten n², kvadratisk kompleksitet, fordi den beskrives af en andengradsfunktion.

Men hvor svært bliver det at kontrollere resultatet? Hvis du svarer mig, at 54 og 17 er tal, hvis produkt giver 918, behøver jeg ikke gennemgå alle talpar fra begge bunker, som du måtte. Det er nok, at jeg ganger dette ene par 54 · 17, så ved jeg, om du har ret eller ej. Så mens der til at løse dette problem skal beregnes op til n² produkter, er det til at kontrollere nok at beregne kun ét produkt. Kontrollen har altså konstant kompleksitet 1.

Her adskiller denne opgave sig kraftigt fra den foregående, hvor vi skulle bruge lige mange trin til selve beregningen og til den efterfølgende kontrol.

Denne opgave er også størrelsesordener sværere end den foregående. Hvis jeg hældte ti tusind sedler ud foran dig og ville finde det mindste tal, kunne du nok finde det på en dag. Men hvis jeg hældte to gange ti tusind sedler ud foran dig og lod dig lede efter produktet, skulle du kontrollere ti tusind gange ti tusind produkter, hvilket er hundrede millioner beregninger. Selv hvis du prøvede ét produkt i sekundet, ville det tage dig omkring tre år.

Problem nr. 3: Summen af en delmængde

Lad os se på det tredje problem. Denne gang hælder jeg tolv sedler med tal ud foran dig, og jeg ville bede dig finde et vilkårligt antal sedler, hvis sum giver nul. For eksempel:

$$A=\{24,-69,1,-15,-76,-60,16,-83,48,-22,54,-47\}$$

Vælg en vilkårlig gruppe af tal blandt disse, hvis sum giver 0. For eksempel tallene

$$24+48-69+1$$

giver summen 4 og er dermed ikke det rigtige svar. Det rigtige svar er gruppen af tal … og ved du hvad? Prøv at finde den selv som lektie 😉. Der findes kun én gruppe af tal, hvis sum giver 0. Så får du i det mindste prøvet, hvor svært dette problem er.

Nu skal vi kende kompleksiteten af dette problem. Selve beregningen er ikke helt triviel længere og er mere for finsmagere. Hvis du er interesseret i, hvordan man kan beregne kompleksiteten af dette problem, så læs videre. Ellers kan du springe til næste afsnit. ⏩

Hvordan kan vi så finde en gruppe af tal, hvis sum giver 0? Jo, vi må simpelthen prøve alle mulige kombinationer af tal. Vi må prøve alle par af tal, alle grupper på tre, fire, fem tal osv., og for hver gruppe må vi kontrollere, om deres sum giver nul. Hvor mange sådanne kombinationer findes der?

Lad os vise det på en mindre mængde af tal. Hvor mange forskellige grupper af tal, altså delmængder, kan jeg danne af de tre tal B = {5, 7, 9}? Der er i alt otte:

$$\begin{array}{rcl}{B}_1& =& \left\{\right\}\\ B_2& =& \left\{5\right\}\\ B_3& =& \left\{7\right\}\\ B_4& =& \left\{9\right\}\\ B_5& =& \{5,9\}\\ B_6& =& \{5,7\}\\ B_7& =& \{7,9\}\\ B_8& =& \{5,7,9\}\end{array}$$

Læg mærke til, at vi også har talt den tomme delmængde B₁ med. Den er ikke særlig nyttig lige nu, men for en ordens skyld lod vi den stå. For at gøre beregningen enklere knytter vi til hver delmængde en binær vektor. En binær vektor er blot en følge af nuller og ettaller, for eksempel 00101010. Vi arbejder med binære vektorer af længde tre. Vi knytter vektoren til delmængden på den måde, at 101 knyttes til den delmængde, der indeholder »det første og tredje tal fra den oprindelige mængde, men ikke det andet tal«, altså mængden {5, 9}. Vektoren 110 knytter vi til den delmængde, der indeholder »det første og andet tal fra den oprindelige mængde, men ikke det tredje«, altså mængden {5, 7} osv.

$$\begin{array}{rcl}{B}_1=\left\{\right\}& \to & 000\\ B_2=\left\{5\right\}& \to & 100\\ B_3=\left\{7\right\}& \to & 010\\ B_4=\left\{9\right\}& \to & 001\\ B_5=\{5,9\}& \to & 101\\ B_6=\{5,7\}& \to & 110\\ B_7=\{7,9\}& \to & 011\\ B_8=\{5,7,9\}& \to & 111\end{array}$$

Vi ser, at hver delmængde har præcis én binær vektor af længde tre. Og hver binær vektor af længde tre svarer til præcis én delmængde. Hvis vi altså beregner, hvor mange forskellige binære vektorer af længde n der findes, får vi antallet af forskellige kombinationer, vi kan sammensætte, hvis vi har n forskellige tal som input. Lad os derfor regne det ud.

Der findes to binære vektorer af længde ét: 0 og 1.

Binære vektorer af længde to får vi ved at tage alle binære vektorer af længde ét og sætte 0 på enden af hver vektor: vi får vektorerne 00 og 10. Igen tager vi alle vektorer af længde 1 og sætter 1 på enden: 01 og 11. Dermed har vi fået alle vektorer af længde 2: 00, 01, 10 og 11.

Binære vektorer af længde tre får vi ved at tage alle binære vektorer af længde to og sætte nul på enden: 000, 010, 100 og 110, og et ettal på enden: 001, 011, 101 og 111.

Og sådan fortsætter vi for hver yderligere længde. Vi ser, at når vi øger længden af den binære vektor med én, fordobles antallet af forskellige binære vektorer. For vektorlængde fire ville vi altså få i alt 2 · 2 · 2 · 2, hvilket er 16, forskellige kombinationer.

Generelt kan vi udlede, at hvis vi har en mængde M, som indeholder n elementer, så er antallet af alle delmængder af denne mængde M lig med antallet af alle forskellige binære vektorer af længde n, og det er lig med

$$\underset{n\text{ gange}}{\underbrace{2\cdot 2\cdot \dots \cdot 2}}=2^n$$

2ⁿ eller n² — er det ikke ligegyldigt? Æbler og pærer 🤷‍♂

Der findes altså 2ⁿ forskellige delmængder, som vi kan danne af en mængde med n tal. I vores tilfælde har vi n = 12 tal og må derfor kontrollere 2¹² forskellige kombinationer, hvilket er 4096 kombinationer. Vi siger, at dette problem har kompleksiteten 2ⁿ, eksponentiel kompleksitet, fordi det beskrives af en eksponentialfunktion.

Læg mærke til, at det foregående problem havde kompleksiteten n², mens dette har kompleksiteten 2ⁿ. Det ligner hinanden meget, ikke? Men der er stor forskel på, om eksponenten er konstant, eller om der står variablen n. Læg mærke til, at når n = 4, får vi

$$\begin{array}{rclrc}{n}^2& =& 4^2& =& 16\\ 2^n& =& 2^4& =& 16\end{array}$$

Okay, indtil videre giver det det samme. Hvad hvis n = 10?

$$\begin{array}{rclrc}{n}^2& =& {10}^2& =& 100\\ 2^n& =& 2^{10}& =& 1024\end{array}$$

Hovsa, eksponentialfunktionen skød i vejret og er pludselig omkring ti gange større end andengradsfunktionen. Hvad får vi for n = 20?

$$\begin{array}{rclrc}{n}^2& =& {20}^2& =& 400\\ 2^n& =& 2^{20}& =& 1.048.576\end{array}$$

Den eksponentielle kompleksitet har for n = 20 en værdi, der er omkring 2600 gange højere end den kvadratiske kompleksitet. Vi ser altså, at eksponentialfunktionen vokser meget hurtigere end andengradsfunktionen. Husk det, næste gang vi rammes af en pandemi, der spreder sig i befolkningen med eksponentiel hastighed.

Hvis jeg altså kastede tyve sedler foran dig, skulle du kontrollere 1.048.576 kombinationer. Det er ret mange.

Hvordan kontrollerer vi resultatets rigtighed?

Hvor lang tid tager det mig at kontrollere, at den resulterende gruppe af tal virkelig giver summen 0? Det går forholdsvis hurtigt, jeg lægger simpelthen denne ene gruppe af tal sammen, og hvis summen er lig med 0, har du fundet den rigtige gruppe sedler, og hvis summen er en anden, har du fundet det forkerte sæt sedler.

Igen ser vi, at det er størrelsesordener lettere at kontrollere resultatet end at finde det.

Problem nr. 4: Handelsrejsendes problem

Handelsrejsendes problem er et af de mest berømte algoritmiske problemer. Groft sagt har vi en handelsrejsende, der sælger regn. Og denne handelsrejsende må rejse meget for at tjene til føden. Han har derfor besluttet at besøge 14 store byer i Danmark. Og fordi han ikke vil spilde noget, har han besluttet at finde den kortest mulige rute, der fører ham gennem alle disse byer. Og vores opgave er at finde den kortest mulige rute.

Hvordan kan vi finde den kortest mulige rute? Vi prøver alle muligheder.

Vi kan gøre det enklere. Lad os forestille os, at der mellem hvert par af byer findes præcis én korteste vej. Hvordan kan vi finde den korteste rute mellem alle byerne? Vi har 14 byer. Vi har altså 14 muligheder for, hvor vi starter. Lad os sige, at vi startede i Aalborg!!! Hvor kan vi komme hen fra Aalborg? Teoretisk kan vi køre til en hvilken som helst anden af byerne. Vi kan altså vælge blandt de 13 tilbageværende byer.

Allerede nu kan vi regne ud, at vi har i alt 14 · 13 muligheder for at besøge de to første byer — vi har 14 muligheder for, hvor vi starter, og derefter kan vi vælge blandt de 13 tilbageværende byer.

Når vi kommer frem til den anden by, må vi fortsætte. Vi har allerede været i to byer, så vi kan rejse videre til en af de 12 tilbageværende byer. Vi har således i alt 14 · 13 · 12 muligheder for at besøge de første tre byer.

Når vi har besøgt den tredje by, må vi vælge en af de 11 tilbageværende byer, derefter en af de 10 tilbageværende byer osv.

Når vi har besøgt dem alle, finder vi ud af, at vi i alt kunne vælge blandt

$$14\cdot 13\cdot 12\cdot 11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1$$

muligheder. Det kan minde dig om fakultet, som vi betegner med et udråbstegn. Vi kan altså sige, at dette produkt er lig med 14!:

$$14!=14\cdot 13\cdot 12\cdot 11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1$$

og der findes altså 14! ruter, der fører gennem alle 14 byer. Er det mange? Ret mange, for

$$14!=87.178.291.200.$$

Generelt gælder, at hvis vi ledte efter den korteste rute mellem n byer, ville vi skulle prøve n! forskellige ruter. Kompleksiteten af denne løsning er altså n!.

Hvordan ville vi kontrollere, at vi har fundet det rigtige resultat? Hvis du fortalte mig, at den korteste rute går fra Esbjerg til Aalborg, derefter til Odense osv., hvordan kan jeg så kontrollere, at du taler sandt? Ja, det er ret svært 🤷‍♂. For når jeg ser på ruten, har jeg ingen nem måde at kontrollere, om netop denne rute er den korteste. Jeg må i grunden udføre hele beregningen igen. Kompleksiteten af at kontrollere resultatet er således også n!.

Klasserne P og NP

Vi har set på fire problemer og de algoritmer, der løser dem, og vi har analyseret, hvor svært det er at finde løsningen, og hvor svært det er at kontrollere denne løsning. Vi kan opsummere det i denne tabel:

Nu deler vi vores problemer op i to grupper. Den første gruppe udgøres af problemer, der er nemme at løse. Det er problemer, der kan løses med kompleksiteten n eller n² eller n³ eller n⁴ osv. Fordi vi kalder udtryk som n² for polynomier, betegner vi denne klasse af problemer med bogstavet P. Vi siger altså, at klassen P indeholder problemer, der kan løses i polynomiel tid (= har kompleksiteten for eksempel n² eller n⁷). Generelt er det problemer, der kan løses mere eller mindre nemt.

Til klassen P hører således problem nr. 1, at finde det mindste tal, fordi det har løsningskompleksiteten n, og dernæst hører problem nr. 2, produktet af et par, med, fordi dets løsningskompleksitet er n², og begge er polynomier.

Den anden klasse er klassen NP. Den indeholder problemer, der kan kontrolleres i polynomiel tid. Til klassen NP hører således alle problemer undtagen det sidste. Handelsrejsendes problem kan vi ikke kontrollere i polynomiel tid. De tre foregående problemer kan kontrolleres i polynomiel tid.

Handelsrejsendes problem kan vi hverken løse eller kontrollere i polynomiel tid. Til handelsrejsendes problem ville vi derfor have brug for endnu en klasse, som indeholdt endnu sværere problemer. Denne klasse findes, men er ikke interessant for os lige nu.

Det er klart, at klassen P er en delmængde af klassen NP. Altså at ethvert problem, der er i klassen P, også er i klassen NP. Det giver mening — hvis vi kan løse et problem i polynomiel tid, kan vi også kontrollere resultatet i polynomiel tid.

Problemet P vs. NP

Og gælder det også omvendt? Er hvert problem fra klassen NP også i klassen P? Altså, hvis der findes en måde at kontrollere resultatet af et problem i polynomiel tid, findes der så også en algoritme, der ville løse det pågældende problem i polynomiel tid?

For eksempel ved vi, at vi kan kontrollere resultatet af problem nr. 3, summen af en delmængde, i polynomiel tid. Men til at løse det brugte vi en algoritme, der ikke er polynomiel, den anvendte algoritme har den eksponentielle kompleksitet 2ⁿ. Men ved vi med sikkerhed, at der ikke findes nogen algoritme med polynomiel kompleksitet til dette problem?

Det ved vi ikke!

Det kunne sagtens være tilfældet, at der for hvert problem, der kan kontrolleres i polynomiel tid, findes en algoritme, som løser dette problem i polynomiel tid. Det ved vi ikke. Vi kan ikke bevise, at en sådan algoritme findes, men vi kan heller ikke modbevise, at den findes.

Hvis der for hvert problem fra klassen NP fandtes en algoritme, der løser det i polynomiel tid, ville det betyde, at klassen NP i virkeligheden var lig med klassen P. Alle problemer fra klassen P ville være i klassen NP, og alle problemer fra klassen NP ville være i klassen P — de to klasser ville være ens, de ville være identiske.

Problemet P vs. NP er altså spørgsmålet, om klassen P er identisk med klassen NP, eller om der er tale om to forskellige klasser af problemer.

Enten gælder altså P = NP, eller også gælder P ≠ NP. Det ved ingen, og hvis du finder ud af det, venter der dig en dusør på en million dollar, udødelig berømmelse og sandsynligvis også Turingprisen, som er en slags Nobelpris for dataloger.

Hvad ville der ske, hvis P = NP?

Hvad ville der ske, hvis det gjaldt, at P = NP? Det er ikke helt let at sige, hvad der ville ske. Vi ville vide, at der for alle problemer fra klassen NP findes en algoritme, der løser dem i polynomiel tid. For eksempel at der for vores problem nr. 3, summen af en delmængde, findes en algoritme, der løser det i polynomiel tid. Men det har tre hager:

• At vi vidste, at en sådan algoritme findes, betyder ikke, at vi er i stand til at finde den. Vi ville simpelthen vide, at ja, der findes en algoritme, som løser problemet i polynomiel tid, men vi ville måske ikke kunne konstruere den i yderligere hundrede år. Det minder om dengang den almene relativitetsteori forudsagde sorte huller, men det alligevel tog os adskillige tiår, før vi kunne tage det første »fotografi« af et sort hul.
• At der findes en algoritme, der arbejder i polynomiel tid, betyder desværre endnu ikke, at den er hurtig. Vi kunne finde en algoritme, der har kompleksiteten n¹⁰⁰. Også udtrykket n¹⁰⁰ er nemlig et polynomium. Når vi sammenligner kompleksiteterne 2ⁿ og n¹⁰⁰, finder vi ud af, at så længe n er forholdsvis lille, skal algoritmen med kompleksiteten 2ⁿ stadig bruge færre operationer. For n = 20 gælder for eksempel, at 2²⁰ = 1.048.576, mens udtrykket 20¹⁰⁰ giver et tal, der har omkring 130 cifre, hvilket er et tal, der er omkring 120 størrelsesordener større end 1.048.576. Vores polynomielle algoritme ville således i virkeligheden være langsommere end den eksponentielle. I det mindste så længe n er forholdsvis lille.
• Hvis det alligevel lykkedes os at finde en hurtig algoritme, der arbejder i polynomiel tid, ville vi kunne løse en masse problemer hurtigere og med større nøjagtighed. Det er selvfølgelig en positiv nyhed, men det har også sine negative sider. Der findes et område, der er afhængigt af, at nogle problemer er svære at løse, og det er kryptografi — kryptering. Det kunne således ske, at det ville blive størrelsesordener lettere at bryde nutidens chifre.

Intermezzo: fordi du har læst helt hertil, afslører jeg som belønning, at løsningen på problem nr. 3 er 24 + 1 − 60 + 16 − 83 + 48 + 54.

Hvad ville der ske, hvis P ≠ NP?

Hvis det gjaldt, at problemklasserne P og NP er forskellige, ville der ikke ske så meget, for det er mere eller mindre status quo. Vi har lige nu ingen algoritme, der løser noget svært problem fra NP i polynomiel tid, og hvis nogen beviste, at P ≠ NP, ville det simpelthen forblive sådan for evigt. Langt mere sensationelt ville et bevis for, at P = NP, være.

Henvisninger i populærkulturen

• I et afsnit af Simpsons kan vi se, at Homer kommer ind i en slags alternativ virkelighed, hvor det åbenbares for ham, at P = NP. Kan ses på youtube.com.
• I Futurama kan vi omvendt se, at de har på lager to mapper, en med navnet P og en med navnet NP. Kan ses på youtube.com.
• Andet afsnit af anden sæson af serien Elementary med titlen »Solve for X« handlede om mordet på en matematiker, som sandsynligvis havde løst problemet P versus NP.