Det største problemet i informatikk: P versus NP

Det finnes sju matematiske problemer som er blitt kalt så vanskelige og interessante at Clay Mathematics Institute har utpekt dem som tusenårsproblemer, og for å løse hvert av dem får løseren en belønning på én million dollar. Ett av problemene berører også informatikken og kalles P versus NP-problemet. La oss forklare hva dette problemet egentlig handler om.

Nåvel. La oss ikke lure oss selv til å tro at det blir enkelt å forklare. Det er tross alt et tusenårsproblem. Så gå og lag en god kopp grønn te 🍵, og la oss sette i gang. Først viser vi fire ulike problemer fra informatikkens og algoritmenes verden. Vi analyserer problemene og ser hvilket forhold de har til bokstavene P og NP.

Problem nr. 1: Å finne det minste tallet

P vs. NP handler om algoritmer og kompleksiteten deres. Tenk deg at jeg helte ut hundre lapper foran deg, med ett tall skrevet på hver av dem, og at jeg ba deg finne lappen med det minste tallet. Hvor lang tid vil det ta deg?

Et halvt minutt? To minutter?

Det er tidsenheter vi egentlig ikke bryr oss så mye om i teoretisk informatikk. Det vi er opptatt av, er heller antall operasjoner. Vi kunne altså spørre litt annerledes: Hvor mange lapper må jeg sjekke for å være sikker på at jeg har funnet det minste tallet? Svaret er at jeg må sjekke alle lappene — fordi det minste tallet kan stå på den siste lappen. Hvis jeg kaster hundre lapper foran deg, må du sjekke hundre lapper. Hvis jeg kaster tusen, må du sjekke tusen. Generelt, hvis jeg kaster n lapper foran deg, må du sjekke n lapper.

Dette kaller vi kompleksiteten til algoritmer. Hvis jeg kaster n lapper foran deg og du må gjøre n operasjoner for å finne det minste tallet, betyr det at denne algoritmen for å finne det minste tallet har kompleksitet n, noe vi også kaller lineær kompleksitet, fordi kompleksiteten beskrives av en lineær funksjon.

Greit, du har gått gjennom hundre lapper og sagt at det minste tallet er 17. Hvordan kan jeg kontrollere at du sier sannheten? Det finnes ingen annen måte enn å gå gjennom alle lappene igjen og kontrollere at det ikke står et mindre tall på noen av dem. Altså, du må se på n lapper for å finne det minste tallet, og når jeg vil kontrollere det, må jeg gjøre det samme. Kompleksiteten til å kontrollere resultatet er dermed også n, lineær kompleksitet.

Finnes det algoritmer der det er enklere å kontrollere resultatet enn å finne det?

Problem nr. 2: Produktet av et par

Tenk deg at jeg heller ut to like store bunker med lapper foran deg, og at det igjen står ett tall på hver lapp. Og nå vil jeg at du skal finne et tall fra bunke A og et tall fra bunke B slik at produktet av dem blir tallet 918. La oss for eksempel ha disse bunkene med tall:

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

Hvordan kan vi finne et par av tall slik at produktet blir lik 918? Vel, vi kan rett og slett prøve alle mulighetene. Hvor mange er det? Ganske mange, det er 25. Vi begynner med å multiplisere det første tallet fra bunke A, altså tallet 49, med hvert tall 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}$$

Ingen av parene gir 918. Vi prøver altså det samme med de resterende tallene fra bunke A, altså fem par til for tallet 11, fem par til for tallet 32, fem par til for 54 og de siste fem parene for 15. Til sammen kan vi prøve 25 par av tall. Til slutt finner vi at 54 · 17 = 918.

Hva er kompleksiteten til denne algoritmen? Vi er interessert i hvor mange par av tall vi måtte multiplisere. Begge bunkene inneholdt fem lapper, og vi måtte prøve hvert av de fem tallene fra den første bunken med hvert av de fem tallene fra den andre bunken. Til sammen prøvde vi 5 · 5 = 25 kombinasjoner. Hvis jeg hadde kastet to bunker med 10 lapper foran deg, måtte du ha prøvd 10 · 10 = 100 kombinasjoner. Generelt, hvis jeg kaster to bunker med n lapper foran deg, må du prøve n · n = n² kombinasjoner.

Vi sier at denne algoritmen vår har kompleksitet n², kvadratisk kompleksitet, fordi den beskrives av en andregradsfunksjon.

Men hvor komplisert blir det å kontrollere resultatet? Hvis du svarer at 54 og 17 er tallene som har produktet 918, trenger jeg ikke gå gjennom alle parene fra begge bunkene slik du måtte. Det holder at jeg multipliserer dette ene paret 54 · 17, så vet jeg om du har rett eller ikke. Så mens det for å løse dette problemet må regnes ut opptil n² produkter, holder det for å kontrollere å regne ut bare ett produkt. Kontrollen har altså konstant kompleksitet 1.

Dermed skiller denne oppgaven seg tydelig fra den forrige, der vi trengte like mange steg til selve utregningen og til den påfølgende kontrollen.

Denne oppgaven er også størrelsesordener vanskeligere enn den forrige. Hvis jeg heller ut ti tusen lapper foran deg og vil at du skal finne det minste tallet, klarer du sannsynligvis å finne det på én dag. Men hvis jeg heller ut to ganger ti tusen lapper og lar deg lete etter et produkt, måtte du kontrollere ti tusen ganger ti tusen produkter, som er hundre millioner utregninger. Selv om du prøvde ett produkt i sekundet, ville det tatt deg omtrent tre år.

Problem nr. 3: Delmengdesummen

La oss se på det tredje problemet. Denne gangen heller jeg ut tolv lapper med tall foran deg, og jeg vil at du skal finne et hvilket som helst antall lapper som har summen null. For eksempel:

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

Velg en hvilken som helst gruppe av tallene som har summen 0. For eksempel gir tallene

$$24+48-69+1$$

summen 4 og er derfor ikke riktig svar. Det riktige svaret er gruppen av tallene… og vet du hva? Prøv å finne den selv som lekse 😉. Det finnes bare én gruppe av tall som har summen 0. Da får du i hvert fall kjenne på hvor vanskelig dette problemet er.

Nå trenger vi å vite kompleksiteten til dette problemet. Selve utregningen er ikke helt triviell og er mest for de spesielt interesserte. Hvis du vil vite hvordan man kan regne ut kompleksiteten til dette problemet, kan du lese videre. Ellers kan du hoppe til neste kapittel. ⏩

Hvordan kan vi altså finne en gruppe av tall som har summen 0? Vel, vi må rett og slett prøve alle mulige kombinasjoner av tall. Vi må prøve alle par av tall, alle grupper på tre, fire, fem osv., og for hver gruppe må vi kontrollere om summen blir null. Hvor mange slike kombinasjoner finnes det?

La oss vise det på en mindre mengde tall. Hvor mange ulike grupper av tall, eller delmengder, kan jeg lage av de tre tallene B = {5, 7, 9}? Det er til sammen åtte:

$$\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}$$

Legg merke til at vi også har regnet med den tomme delmengden B₁. Den er ikke veldig nyttig akkurat nå, men vi har latt den stå for ordens skyld. For å gjøre utregningen enklere tilordner vi hver delmengde en binær vektor. En binær vektor er rett og slett en følge av nuller og enere, for eksempel 00101010. Vi skal arbeide med binære vektorer med lengde tre. Vi tilordner vektoren slik at 101 tilordnes delmengden som inneholder «det første og det tredje tallet fra den opprinnelige mengden, men ikke det andre tallet», altså mengden {5, 9}. Vektoren 110 tilordnes delmengden som inneholder «det første og det andre tallet fra den opprinnelige mengden, men ikke det tredje», altså mengden {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 delmengde har nøyaktig én binær vektor med lengde tre. Og hver binær vektor med lengde tre svarer til nøyaktig én delmengde. Hvis vi altså regner ut hvor mange ulike binære vektorer med lengde n det finnes, får vi antallet ulike kombinasjoner vi kan sette sammen når vi har n ulike tall som inndata. La oss regne det ut.

Det finnes to binære vektorer med lengde én: 0 og 1.

Binære vektorer med lengde to får vi ved å ta alle binære vektorer med lengde én og sette 0 på slutten av hver vektor: Vi får vektorene 00 og 10. Så tar vi alle vektorene med lengde 1 på nytt og setter 1 på slutten: 01 og 11. Dermed har vi fått alle vektorene med lengde 2: 00, 01, 10 og 11.

Binære vektorer med lengde tre får vi ved å ta alle binære vektorer med lengde to og sette en null på slutten: 000, 010, 100 og 110, og en ener: 001, 011, 101 og 111.

Og slik fortsetter vi for hver ny lengde. Vi ser at når vi øker lengden på den binære vektoren med én, dobles antallet ulike binære vektorer. For vektorlengde fire ville vi altså få til sammen 2 · 2 · 2 · 2, som er 16, ulike kombinasjoner.

Generelt kan vi utlede at hvis vi har en mengde M som inneholder n elementer, er antallet av alle delmengder av denne mengden M lik antallet av alle ulike binære vektorer med lengde n, og det er lik

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

2ⁿ eller n² — er det ikke det samme? Hipp som happ 🤷‍♂

Det finnes altså 2ⁿ ulike delmengder vi kan lage av en mengde med n tall. I vårt tilfelle har vi n = 12 tall, og vi må derfor kontrollere 2¹² ulike kombinasjoner, som er 4096 kombinasjoner. Vi sier at dette problemet har kompleksitet 2ⁿ, eksponentiell kompleksitet, fordi det beskrives av en eksponentialfunksjon.

Legg merke til at det forrige problemet hadde kompleksitet n², mens dette har kompleksitet 2ⁿ. Det ser veldig likt ut, ikke sant? Men det er stor forskjell på om eksponenten er konstant, og om den er variabelen n. Legg merke til at når n = 4, får vi

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

Greit, til nå blir det like. Hva om n = 10?

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

Oi, eksponentialfunksjonen har skutt i været og er plutselig omtrent ti ganger større enn andregradsfunksjonen. Hva får vi for n = 20?

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

Eksponentiell kompleksitet har for n = 20 omtrent 2600 ganger så høy verdi som kvadratisk kompleksitet. Vi ser altså at eksponentialfunksjonen vokser mye raskere enn andregradsfunksjonen. Husk det neste gang vi rammes av en pandemi som sprer seg i befolkningen med eksponentiell hastighet.

Hvis jeg altså kastet tjue lapper foran deg, måtte du kontrollere 1 048 576 kombinasjoner. Det er ganske mye.

Hvordan kontrollerer vi at resultatet er riktig?

Hvor lang tid vil det ta meg å kontrollere at den gruppen av tall du fant, virkelig har summen 0? Det går ganske raskt, jeg legger rett og slett sammen denne ene gruppen av tall, og hvis summen er lik 0, har du funnet den riktige gruppen av lapper, og hvis summen er en annen, fant du feil sett med lapper.

Igjen ser vi at det er størrelsesordener enklere å kontrollere et resultat enn å finne det.

Problem nr. 4: Handelsreisendes problem

Handelsreisendes problem er et av de mest berømte algoritmiske problemene. Grovt sagt har vi en handelsreisende som selger regn. Og denne handelsreisende må reise mye for å tjene til livets opphold. Han har derfor bestemt seg for å besøke 14 store byer i Norge. Og siden han ikke vil kaste bort noe, har han bestemt seg for å finne den korteste mulige ruten som tar ham gjennom alle disse byene. Og oppgaven vår er å finne denne korteste ruten.

Hvordan kan vi finne denne korteste ruten? Vi prøver alle mulighetene.

Vi kan forenkle det. La oss tenke oss at det mellom to hvilke som helst av byene finnes nøyaktig én korteste vei. Hvordan kan vi finne den korteste ruten mellom alle byene? Vi har 14 byer. Vi har altså 14 muligheter for hvor vi kan begynne. La oss si at vi begynte i Trondheim!!! Hvor kan vi komme oss fra Trondheim? Teoretisk kan vi reise til en hvilken som helst av de andre byene. Vi kan altså velge blant de 13 gjenværende byene.

Allerede nå kan vi regne ut at vi har til sammen 14 · 13 muligheter for hvordan vi kan besøke de to første byene — vi har 14 muligheter for hvor vi kan begynne, og så kan vi velge blant de 13 gjenværende byene.

Når vi kommer til den andre byen, må vi fortsette videre. Vi har allerede vært i to byer, så vi kan reise til én av de 12 gjenværende byene. Vi har dermed til sammen 14 · 13 · 12 muligheter for hvordan vi kan besøke de tre første byene.

Når vi har besøkt den tredje byen, må vi velge én av de 11 gjenværende byene, så én av de 10 gjenværende byene osv.

Når vi har besøkt alle, finner vi at vi til sammen hadde å velge mellom

$$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$$

muligheter. Det kan minne deg om fakultet, som vi skriver med utropstegn. Vi kan altså si at dette produktet er lik 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 det finnes altså 14! ruter som går gjennom alle de 14 byene. Er det mye? Ganske mye, for

$$14!=87178291200.$$

Generelt, hvis vi lette etter den korteste ruten mellom n byer, måtte vi prøve n! ulike ruter. Kompleksiteten til denne løsningen er dermed n!.

Hvordan ville vi kontrollert at vi har funnet riktig resultat? Hvis du sa til meg at den korteste ruten går fra Stavanger til Tromsø, så til Bergen osv., hvordan kan jeg kontrollere at du forteller meg sannheten? Vel, det er ganske vanskelig 🤷‍♂. For når jeg ser på ruten, har jeg ingen enkel måte å kontrollere om akkurat denne ruten er den korteste. Jeg må egentlig gjøre hele utregningen på nytt. Kompleksiteten til å kontrollere resultatet er dermed også n!.

Klassene P og NP

Vi har sett på fire problemer og algoritmene som løser dem, og vi har analysert hvor vanskelig det er å finne løsningen og hvor vanskelig det er å kontrollere løsningen. Vi kan oppsummere det i denne tabellen:

Nå deler vi problemene våre inn i to grupper. Den første gruppen består av problemer som er enkle å løse. Det er problemer som kan løses med kompleksitet n eller n² eller n³ eller n⁴ osv. Siden uttrykk som n² kalles polynomer, betegner vi denne klassen av problemer med bokstaven P. Vi sier altså at klassen P inneholder problemer som kan løses i polynomisk tid (= har kompleksitet for eksempel n² eller n⁷). Generelt er det problemer som kan løses mer eller mindre enkelt.

Til klassen P hører dermed problem nr. 1, å finne det minste tallet, fordi det har løsningskompleksitet n, og så hører problem nr. 2, produktet av et par, dit, fordi løsningskompleksiteten er n², og begge er polynomer.

Den andre klassen er klassen NP. Den inneholder problemer som kan kontrolleres i polynomisk tid. Til klassen NP hører dermed alle problemene unntatt det siste. Handelsreisendes problem klarer vi ikke å kontrollere i polynomisk tid. De tre foregående problemene kan kontrolleres i polynomisk tid.

Handelsreisendes problem klarer vi hverken å løse eller kontrollere i polynomisk tid. For handelsreisendes problem trenger vi altså enda en klasse, som inneholder enda vanskeligere problemer. Denne klassen finnes, men den er ikke interessant for oss akkurat nå.

Det er åpenbart at klassen P er en delmengde av klassen NP. Altså at hvert problem som ligger i klassen P, også ligger i klassen NP. Det gir mening — hvis vi klarer å løse et problem i polynomisk tid, klarer vi også å kontrollere resultatet i polynomisk tid.

P vs. NP-problemet

Men gjelder det også omvendt? Ligger hvert problem fra klassen NP også i klassen P? Altså, hvis det finnes en måte å kontrollere resultatet av et problem i polynomisk tid, finnes det da også en algoritme som løser problemet i polynomisk tid?

For eksempel vet vi at vi klarer å kontrollere resultatet av problem nr. 3, delmengdesummen, i polynomisk tid. Men for å løse det brukte vi en algoritme som ikke er polynomisk, algoritmen vi brukte, har eksponentiell kompleksitet 2ⁿ. Men vet vi sikkert at det ikke finnes noen algoritme med polynomisk kompleksitet for dette problemet?

Det vet vi ikke!

Det kan godt hende at det for hvert problem som kan kontrolleres i polynomisk tid, finnes en algoritme som løser dette problemet i polynomisk tid. Vi vet det ikke. Vi klarer ikke å bevise at en slik algoritme finnes, men vi klarer heller ikke å motbevise at den finnes.

Hvis det for hvert problem i klassen NP fantes en algoritme som løser det i polynomisk tid, ville det bety at klassen NP egentlig var lik klassen P. Alle problemer fra klassen P ville ligge i klassen NP, og alle problemer fra klassen NP ville ligge i klassen P — de to klassene ville være like, de ville være sammenfallende.

P vs. NP-problemet er altså spørsmålet om klassen P er lik klassen NP, eller om det er to ulike klasser av problemer.

Enten gjelder altså P = NP, eller så gjelder P ≠ NP. Ingen vet hvilket, og hvis du finner ut av det, venter en million dollar i belønning, udødelig berømmelse og sannsynligvis også Turingprisen, som er en slags nobelpris for informatikere.

Hva ville skjedd hvis P = NP?

Hva ville skjedd hvis det gjaldt at P = NP? Vel, det er ikke helt enkelt å si hva som ville skjedd. Vi ville vite at det for alle problemer fra klassen NP finnes en algoritme som løser dem i polynomisk tid. For eksempel at det for problem nr. 3, delmengdesummen, finnes en algoritme som løser det i polynomisk tid. Men det er tre forbehold:

• At vi ville vite at en slik algoritme finnes, betyr ikke at vi klarer å finne den. Vi ville rett og slett vite at ja, det finnes en algoritme som løser problemet i polynomisk tid, men vi ville kanskje ikke klare å konstruere den på hundre år til. Det er litt som da den generelle relativitetsteorien forutså at sorte hull finnes, men det likevel tok oss flere tiår før vi klarte å ta det første «fotografiet» av et sort hull.
• At det finnes en algoritme som arbeider i polynomisk tid, betyr dessverre ikke at den er rask. Vi kunne finne en algoritme som har kompleksitet n¹⁰⁰. For også uttrykket n¹⁰⁰ er et polynom. Når vi sammenligner kompleksitetene 2ⁿ og n¹⁰⁰, finner vi at så lenge n er relativt lite, trenger algoritmen med kompleksitet 2ⁿ fortsatt færre operasjoner. For eksempel gjelder det for n = 20 at 2²⁰ = 1 048 576, mens uttrykket 20¹⁰⁰ gir et tall som har omtrent 130 sifre, og det er et tall som er omtrent 120 størrelsesordener større enn 1 048 576. Den polynomiske algoritmen vår ville dermed i praksis vært tregere enn den eksponentielle. I hvert fall så lenge n er relativt lite.
• Hvis vi likevel klarte å finne en rask algoritme som arbeider i polynomisk tid, ville vi klart å løse mange problemer raskere og mer nøyaktig. Det er selvsagt en positiv nyhet, men den har også sine negative sider. Det finnes et fagfelt som støtter seg på at enkelte problemer er vanskelige å løse, og det er kryptografi — kryptering. Det kunne altså skje at det ble størrelsesordener enklere å knekke dagens chiffer.

Intermesso: Siden du har lest helt hit, avslører jeg som belønning at løsningen på problem nr. 3 er 24 + 1 − 60 + 16 − 83 + 48 + 54.

Hva ville skjedd hvis P ≠ NP?

Hvis det gjaldt at klassene av problemer P og NP er ulike, ville det ikke skjedd så mye, for det er mer eller mindre status quo. Akkurat nå har vi ingen algoritme som løser noe vanskelig problem fra NP i polynomisk tid, og hvis noen beviste at P ≠ NP, ville det rett og slett forbli slik for alltid. Et bevis for at P = NP ville vært en langt større sensasjon.

Henvisninger i populærkulturen

• I en episode av Simpsons ser vi at Homer havner i en slags alternativ virkelighet, der det åpenbares for ham at P = NP. Se på youtube.com.
• I Futurama derimot ser vi at de har to mapper på lageret, én med navnet P og én med navnet NP. Se på youtube.com.
• Den andre episoden i den andre sesongen av serien Elementary med tittelen «Solve for X» handlet om drapet på en matematiker som sannsynligvis hadde løst P versus NP-problemet.