Het grootste probleem in de informatica: P versus NP

Er zijn zeven wiskundige problemen die zo moeilijk en interessant werden gevonden dat het Clay Mathematics Institute ze millenniumproblemen heeft genoemd. Wie er een oplost, krijgt een beloning van een miljoen dollar. Een van die problemen raakt ook aan de informatica en heet het probleem P versus NP. We leggen uit waar dit probleem eigenlijk over gaat.

Laten we eerlijk zijn: we gaan onszelf niet wijsmaken dat het eenvoudig uit te leggen is. Het is tenslotte een millenniumprobleem. Zet dus maar een lekker kopje groene thee 🍵 en laten we beginnen. Eerst laten we vier verschillende problemen uit de wereld van de informatica en algoritmen zien. We analyseren de problemen en kijken welk verband ze hebben met de letters P en NP.

Probleem 1: het kleinste getal vinden

P versus NP gaat over algoritmen en hun complexiteit. Stel je voor dat ik honderd briefjes voor je neergooi, op elk briefje staat één getal, en dat ik je vraag het briefje te vinden waarop het kleinste getal staat. Hoe lang duurt dat?

Een halve minuut? Twee minuten?

Dat zijn tijdseenheden waar we in de theoretische informatica niet zo in geïnteresseerd zijn. Wat ons interesseert, is eerder het aantal bewerkingen. We kunnen de vraag dus iets anders stellen: hoeveel briefjes moet ik bekijken om zeker te weten dat ik het kleinste getal heb gevonden? Het antwoord is dat ik alle briefjes moet bekijken, want het kleinste getal kan op het laatste briefje staan. Als ik honderd briefjes voor je neergooi, moet je honderd briefjes bekijken. Als ik er duizend neergooi, moet je er duizend bekijken. In het algemeen geldt: als ik n briefjes voor je neergooi, moet je n briefjes bekijken.

Dit noemen we de complexiteit van algoritmen. Als ik n briefjes voor je neergooi en jij n bewerkingen moet doen om het kleinste getal te vinden, betekent dat dat dit algoritme voor het zoeken van het kleinste getal complexiteit n heeft. Dat noemen we ook lineaire complexiteit, omdat de complexiteit wordt beschreven door een lineaire functie.

Goed, je hebt honderd briefjes doorgenomen en meldt dat het kleinste getal 17 is. Hoe kan ik controleren of je de waarheid spreekt? Er is geen andere manier dan opnieuw alle briefjes door te nemen en te controleren dat er op geen enkel briefje een kleiner getal staat. Jij moet dus naar n briefjes kijken om het kleinste getal te vinden, en als ik het wil controleren, moet ik hetzelfde doen. De complexiteit van het controleren van het resultaat is dus ook n, lineaire complexiteit.

Bestaan er algoritmen waarbij het eenvoudiger is om het resultaat te controleren dan om het te vinden?

Probleem 2: het product van een paar

Stel je voor dat ik twee even grote stapels briefjes voor je neergooi, op elk briefje weer één getal. Nu zou ik willen dat je een getal uit stapel A en een getal uit stapel B vindt, zodat hun product 918 is. Laten we bijvoorbeeld deze stapels getallen nemen:

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

Hoe kunnen we een paar getallen vinden waarvan het product gelijk is aan 918? Nou, we kunnen gewoon alle mogelijkheden proberen. Hoeveel zijn dat er? Best veel, namelijk 25. We beginnen met het eerste getal uit stapel A, dus 49, te vermenigvuldigen met elk getal uit stapel 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}$$

Geen enkel paar geeft 918. We proberen dus hetzelfde met de overige getallen uit stapel A, dus nog vijf paren voor het getal 11, nog vijf paren voor het getal 32, nog vijf paren voor 54 en de laatste vijf paren voor 15. In totaal kunnen we zo 25 paren getallen proberen. Uiteindelijk vinden we dat 54 · 17 = 918.

Wat is de complexiteit van dit algoritme? We zijn geïnteresseerd in hoeveel paren getallen we moesten vermenigvuldigen. Beide stapels bevatten vijf briefjes en we moesten elk van de vijf getallen uit de eerste stapel met elk van de vijf getallen uit de tweede stapel proberen. In totaal hebben we 5 · 5 = 25 combinaties geprobeerd. Als ik twee stapels van 10 briefjes voor je neergooi, moet je 10 · 10 = 100 combinaties proberen. Algemeen: als ik twee stapels van n briefjes voor je neergooi, moet je n · n = n² combinaties proberen.

We zeggen dat ons algoritme complexiteit n² heeft, kwadratische complexiteit, omdat die wordt beschreven door een kwadratische functie.

Maar hoe moeilijk is het om het resultaat te controleren? Als je me antwoordt dat 54 en 17 de getallen zijn waarvan het product 918 is, hoef ik niet alle paren getallen uit beide stapels langs te lopen, zoals jij moest doen. Het is genoeg als ik dit ene paar 54 · 17 vermenigvuldig, dan weet ik of je gelijk hebt of niet. Terwijl er dus voor het oplossen van dit probleem tot wel n² producten moeten worden uitgerekend, is voor het controleren maar één product nodig. Het controleren heeft dus constante complexiteit 1.

Hierin verschilt deze opgave sterk van de vorige, waar we voor het zelf uitrekenen en voor het controleren daarna evenveel stappen nodig hadden.

Deze opgave is ook een orde van grootte ingewikkelder dan de vorige. Als ik tienduizend briefjes voor je neergooi en je moet het kleinste getal vinden, kun je dat waarschijnlijk in één dag. Maar als ik tweemaal tienduizend briefjes voor je neergooi en je laat zoeken naar een product, zou je tienduizend keer tienduizend producten moeten controleren, dat zijn honderd miljoen berekeningen. Zelfs als je één product per seconde zou uitrekenen, zou het je ongeveer drie jaar kosten.

Probleem 3: de som van een deelverzameling

Laten we het derde probleem bekijken. Deze keer gooi ik twaalf briefjes met getallen voor je neer en ik zou willen dat je een willekeurig aantal briefjes vindt waarvan de som nul is. Bijvoorbeeld:

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

Kies uit deze getallen een willekeurige groep getallen waarvan de som 0 is. De getallen

$$24+48-69+1$$

hebben bijvoorbeeld som 4 en zijn dus niet het juiste antwoord. Het juiste antwoord is de groep getallen… en weet je wat? Zoek het zelf maar uit als huiswerk 😉. Er bestaat precies één groep getallen waarvan de som 0 is. Dan ervaar je in elk geval hoe moeilijk dit probleem is.

Nu moeten we de complexiteit van dit probleem kennen. Het uitrekenen zelf is niet helemaal triviaal en is meer iets voor fijnproevers. Als je wilt weten hoe je de complexiteit van dit probleem kunt berekenen, lees dan verder. Anders kun je doorgaan naar het volgende hoofdstuk. ⏩

Hoe kunnen we dus een groep getallen vinden waarvan de som 0 is? Nou, we moeten gewoon alle mogelijke combinaties van getallen proberen. We moeten alle paren getallen proberen, alle drietallen, viertallen, vijftallen enzovoort, en bij elke groep controleren of de som nul is. Hoeveel van zulke combinaties zijn er?

Laten we het laten zien aan een kleinere verzameling getallen. Hoeveel verschillende groepen getallen, oftewel deelverzamelingen, kan ik maken van de drie getallen B = {5, 7, 9}? In totaal zijn dat er acht:

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

Merk op dat we ook de lege deelverzameling B₁ hebben meegeteld. Dat is nu niet erg nuttig, maar voor de volledigheid hebben we haar erbij gelaten. Om de berekening te vereenvoudigen, koppelen we aan elke deelverzameling een binaire vector. Een binaire vector is gewoon een rij nullen en enen, bijvoorbeeld 00101010. Wij werken met binaire vectoren van lengte drie. We koppelen de vector zo dat we 101 koppelen aan de deelverzameling die “het eerste en het derde getal uit de oorspronkelijke verzameling bevat, maar niet het tweede getal”, dus aan de verzameling {5, 9}. De vector 110 koppelen we aan de deelverzameling die “het eerste en het tweede getal uit de oorspronkelijke verzameling bevat, maar niet het derde”, dus aan de verzameling {5, 7} enzovoort.

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

We zien dat elke deelverzameling precies één binaire vector van lengte drie heeft. En elke binaire vector van lengte drie hoort bij precies één deelverzameling. Als we dus berekenen hoeveel verschillende binaire vectoren van lengte n er bestaan, krijgen we het aantal verschillende combinaties dat we kunnen maken als we n verschillende getallen als invoer hebben. Laten we dat uitrekenen.

Binaire vectoren van lengte één zijn er twee: 0 en 1.

Binaire vectoren van lengte twee krijgen we door alle binaire vectoren van lengte één te nemen en aan het einde van elke vector een 0 toe te voegen: we krijgen de vectoren 00 en 10. Opnieuw nemen we alle vectoren van lengte 1 en voegen aan het einde een 1 toe: 01 en 11. Zo hebben we alle vectoren van lengte 2: 00, 01, 10 en 11.

Binaire vectoren van lengte drie krijgen we door alle binaire vectoren van lengte twee te nemen en aan het einde een nul toe te voegen: 000, 010, 100 en 110, en een één: 001, 011, 101 en 111.

En zo gaat dat door voor elke volgende lengte. We zien dat als we de lengte van de binaire vector met één verhogen, het aantal verschillende binaire vectoren verdubbelt. Voor vectoren van lengte vier krijgen we dus in totaal 2 · 2 · 2 · 2, dat is 16, verschillende combinaties.

In het algemeen kunnen we afleiden dat als we een verzameling M hebben met n elementen, het aantal deelverzamelingen van deze verzameling M gelijk is aan het aantal verschillende binaire vectoren van lengte n, en dat is gelijk aan

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

2ⁿ of n² — is dat niet hetzelfde? Appels en peren 🤷‍♂

Er bestaan dus 2ⁿ verschillende deelverzamelingen die we kunnen maken uit een verzameling van n getallen. In ons geval hebben we n = 12 getallen en moeten we dus 2¹² verschillende combinaties controleren, dat zijn 4096 combinaties. We zeggen dat dit probleem complexiteit 2ⁿ heeft, exponentiële complexiteit, omdat het wordt beschreven door een exponentiële functie.

Merk op dat het vorige probleem complexiteit n² had, terwijl dit probleem complexiteit 2ⁿ heeft. Dat lijkt erg op elkaar, toch? Maar het is een groot verschil of de exponent constant is of dat daar de variabele n staat. Merk op dat we voor n = 4 krijgen

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

Goed, tot nu toe komt er hetzelfde uit. Wat als n = 10?

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

Tjonge, de exponentiële functie schiet omhoog en is ineens ongeveer tien keer zo groot als de kwadratische. Wat krijgen we voor n = 20?

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

De exponentiële complexiteit heeft voor n = 20 een waarde die ongeveer 2600 keer zo hoog is als de kwadratische complexiteit. We zien dus dat een exponentiële functie veel sneller groeit dan een kwadratische functie. Denk hieraan als ons weer eens een pandemie treft die zich met exponentiële snelheid onder de bevolking verspreidt.

Als ik dus twintig briefjes voor je neergooi, zou je 1 048 576 combinaties moeten controleren. Dat is best veel.

Hoe controleren we of het resultaat klopt?

Hoe lang duurt het om te controleren of de gevonden groep getallen echt som 0 heeft? Dat gaat vrij snel: ik tel gewoon deze ene groep getallen op en als de som 0 is, heb je de juiste groep briefjes gevonden, en als de som anders is, heb je de verkeerde set briefjes gevonden.

Opnieuw zien we dat het controleren van het resultaat een orde van grootte eenvoudiger is dan het vinden ervan.

Probleem 4: het handelsreizigersprobleem

Het handelsreizigersprobleem is een van de beroemdste algoritmische problemen. Grofweg hebben we een handelsreiziger die regen verkoopt. En deze handelsreiziger moet veel reizen om de kost te verdienen. Daarom besluit hij elke provinciehoofdstad in Nederland te bezoeken. En omdat hij niets wil verspillen, besluit hij de kortst mogelijke route te zoeken die hem langs alle provinciehoofdsteden in het land voert. En onze taak is om zo'n kortste route te vinden.

Hoe kunnen we deze kortste route vinden? We proberen alle mogelijkheden.

We kunnen het onszelf makkelijker maken. Stel dat er tussen elke twee provinciehoofdsteden precies één kortste weg bestaat. Hoe kunnen we de kortste route langs alle steden vinden? We hebben 12 provinciehoofdsteden. We hebben dus 12 mogelijkheden om te beginnen. Stel dat we in Maastricht zijn begonnen!!! Waar kunnen we vanuit Maastricht naartoe? In theorie kunnen we naar elke andere provinciehoofdstad reizen. We kunnen dus kiezen uit de 11 overige steden.

Nu kunnen we al uitrekenen dat we in totaal 12 · 11 mogelijkheden hebben om de eerste twee provinciehoofdsteden te bezoeken: we hebben 12 mogelijkheden om te beginnen en dan kunnen we kiezen uit de 11 overige provinciehoofdsteden.

Als we in de tweede stad aankomen, moeten we verder. In twee steden zijn we al geweest, dus we kunnen naar een van de 10 overige steden reizen. We hebben zo in totaal 12 · 11 · 10 mogelijkheden om de eerste drie steden te bezoeken.

Als we de derde provinciehoofdstad hebben bezocht, moeten we een van de 9 overige steden kiezen, dan een van de 8 overige steden enzovoort.

Als we ze allemaal hebben bezocht, blijkt dat we in totaal konden kiezen uit

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

mogelijkheden. Dat doet je misschien denken aan de faculteit, die we met een uitroepteken noteren. We kunnen dus zeggen dat dit product gelijk is aan 12!:

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

en er bestaan dus 12! routes die langs alle provinciehoofdsteden van Nederland voeren. Is dat veel? Best wel, want

$$12!=479001600.$$

In het algemeen zouden we, als we de kortste route tussen n steden zochten, n! verschillende routes moeten proberen. De complexiteit van die oplossing is dus n!.

Hoe zouden we controleren of we het juiste resultaat hebben gevonden? Als je me zou zeggen dat de kortste route van Groningen naar Maastricht loopt, dan naar Zwolle enzovoort, hoe kan ik dan controleren of je de waarheid spreekt? Nou, dat is lastig 🤷‍♂. Want als ik naar die route kijk, kan ik niet makkelijk nagaan of juist deze route de kortste is. Ik moet eigenlijk de hele berekening opnieuw doen. De complexiteit van het controleren van het resultaat is dus ook n!.

De klassen P en NP

We hebben vier problemen en de algoritmen die ze oplossen leren kennen en we hebben geanalyseerd hoe moeilijk het is om een oplossing te vinden en hoe moeilijk het is om die oplossing te controleren. We kunnen dat samenvatten in deze tabel:

Nu verdelen we onze problemen in twee groepen. De eerste groep bestaat uit problemen die eenvoudig op te lossen zijn. Dat zijn problemen die je kunt oplossen met complexiteit n of n² of n³ of n⁴ enzovoort. Omdat uitdrukkingen als n² veeltermen (polynomen) heten, noemen we deze klasse van problemen P. We zeggen dus dat de klasse P de problemen bevat die in polynomiale tijd op te lossen zijn (= complexiteit bijvoorbeeld n² of n⁷). In het algemeen zijn dat problemen die min of meer eenvoudig op te lossen zijn.

Tot de klasse P behoren dus probleem 1, het vinden van het kleinste getal, omdat dat complexiteit n heeft, en probleem 2, het product van een paar, omdat de complexiteit van het oplossen n² is, en beide zijn veeltermen.

De tweede klasse is de klasse NP. Die bevat problemen die in polynomiale tijd te controleren zijn. Tot de klasse NP behoren dus alle problemen, behalve het laatste. Het handelsreizigersprobleem kunnen we niet in polynomiale tijd controleren. De eerste drie problemen zijn wel in polynomiale tijd te controleren.

Het handelsreizigersprobleem kunnen we niet in polynomiale tijd oplossen en ook niet controleren. Voor het handelsreizigersprobleem zouden we dus nog een andere klasse nodig hebben, met nog moeilijkere problemen. Die klasse bestaat, maar is voor ons nu niet interessant.

Het is duidelijk dat de klasse P een deelverzameling is van de klasse NP. Dat wil zeggen dat elk probleem in de klasse P ook in de klasse NP zit. Dat is logisch: als we een probleem in polynomiale tijd kunnen oplossen, kunnen we het resultaat ook in polynomiale tijd controleren.

Het P-versus-NP-probleem

En geldt het ook omgekeerd? Zit elk probleem uit de klasse NP ook in de klasse P? Dus: als er een manier is om het resultaat van een probleem in polynomiale tijd te controleren, bestaat er dan ook een algoritme dat het probleem in polynomiale tijd oplost?

We weten bijvoorbeeld dat we het resultaat van probleem 3, de som van een deelverzameling, in polynomiale tijd kunnen controleren. Maar om het op te lossen hebben we een algoritme gebruikt dat niet polynomiaal is: het gebruikte algoritme heeft exponentiële complexiteit 2ⁿ. Maar weten we zeker dat er voor dit probleem geen enkel algoritme met polynomiale complexiteit bestaat?

Dat weten we niet!

Het zou best kunnen dat er voor elk probleem dat in polynomiale tijd te controleren is, een algoritme bestaat dat dit probleem in polynomiale tijd oplost. Wij weten het niet. We kunnen het bestaan van zo'n algoritme niet bewijzen, maar we kunnen het bestaan ervan ook niet weerleggen.

Als er voor elk probleem uit de klasse NP een algoritme zou bestaan dat het in polynomiale tijd oplost, zou dat betekenen dat de klasse NP eigenlijk gelijk is aan de klasse P. Alle problemen uit de klasse P zouden in de klasse NP zitten en alle problemen uit de klasse NP zouden in de klasse P zitten: beide klassen zouden gelijk zijn, ze zouden samenvallen.

Het P-versus-NP-probleem is dus de vraag of de klasse P gelijk is aan de klasse NP, of dat het om twee verschillende klassen van problemen gaat.

Er geldt dus óf P = NP, óf P ≠ NP. Niemand weet welke van de twee, en als jij erachter komt, wacht je een beloning van een miljoen dollar, onsterfelijke roem en waarschijnlijk ook de Turing Award, een soort Nobelprijs voor informatici.

Wat zou er gebeuren als P = NP?

Wat zou er gebeuren als P = NP zou gelden? Nou, het is niet helemaal eenvoudig te zeggen wat er zou gebeuren. We zouden weten dat er voor alle problemen uit de klasse NP een algoritme bestaat dat ze in polynomiale tijd oplost. Bijvoorbeeld dat er voor ons probleem 3, de som van een deelverzameling, een algoritme bestaat dat het in polynomiale tijd oplost. Maar daar zitten drie addertjes aan:

• Dat we zouden weten dat zo'n algoritme bestaat, betekent niet dat we het kunnen vinden. We zouden gewoon weten dat er inderdaad een algoritme bestaat dat het probleem in polynomiale tijd oplost, maar we zouden het misschien nog wel honderd jaar niet kunnen construeren. Het is vergelijkbaar met hoe de algemene relativiteitstheorie het bestaan van zwarte gaten voorspelde, maar het toch nog enkele tientallen jaren duurde voordat we de eerste “foto” van een zwart gat konden maken.
• Dat er een algoritme bestaat dat in polynomiale tijd werkt, betekent helaas nog niet dat het snel is. We zouden een algoritme kunnen vinden met complexiteit n¹⁰⁰. Ook de uitdrukking n¹⁰⁰ is namelijk een veelterm. Als we de complexiteiten 2ⁿ en n¹⁰⁰ vergelijken, blijkt dat zolang n relatief klein is, het algoritme met complexiteit 2ⁿ nog steeds minder bewerkingen nodig heeft. Voor n = 20 geldt bijvoorbeeld dat 2²⁰ = 1 048 576, terwijl de uitdrukking 20¹⁰⁰ leidt tot een getal van ongeveer 130 cijfers, dat ongeveer 120 ordes van grootte groter is dan 1 048 576. Ons polynomiale algoritme zou in de praktijk dus langzamer zijn dan het exponentiële. Althans zolang n relatief klein is.
• Als het ons toch zou lukken een snel algoritme te vinden dat in polynomiale tijd werkt, zouden we heel wat problemen sneller en nauwkeuriger kunnen oplossen. Dat is natuurlijk goed nieuws, maar het heeft ook zijn nadelen. Er is een vakgebied dat erop vertrouwt dat sommige problemen moeilijk op te lossen zijn, en dat is cryptografie, het versleutelen van gegevens. Het zou dus kunnen gebeuren dat het een orde van grootte eenvoudiger wordt om de huidige versleutelingen te kraken.

Intermezzo: omdat je tot hier hebt doorgelezen, verklap ik je als beloning dat de oplossing van probleem 3 24 + 1 − 60 + 16 − 83 + 48 + 54 is.

Wat zou er gebeuren als P ≠ NP?

Als de klassen P en NP verschillend zouden zijn, zou er niet zoveel gebeuren, want dat is min of meer de status quo. Wij hebben op dit moment geen algoritme dat een moeilijk probleem uit NP in polynomiale tijd oplost, en als iemand zou bewijzen dat P ≠ NP, zou dat gewoon voor altijd zo blijven. Het bewijs dat P = NP zou veel meer sensatie veroorzaken.

Verwijzingen in de popcultuur

• In een aflevering van De Simpsons zien we dat Homer in een soort alternatieve werkelijkheid terechtkomt, waarin hem wordt geopenbaard dat P = NP. Te zien op youtube.com.
• In Futurama zien we daarentegen dat ze in het magazijn twee mappen hebben, een met de naam P en een met de naam NP. Te zien op youtube.com.
• De tweede aflevering van het tweede seizoen van de serie Elementary, met de titel “Solve for X”, gaat over de moord op een wiskundige die waarschijnlijk het P-versus-NP-probleem heeft opgelost.