#WiskundePlantyn

Wiskunde in de Simpsons (7): over makkelijk en moeilijk

Zijn de klassen P en NP gelijk?

De Simpsons is niet alleen ’s werelds meest iconische animatieserie, maar barst ook van wiskundige finessen. Tot de schrijvers behoren Stewart Burns (master in wiskunde), David X Cohen (master in informatica), Ken Keeler (PhD in toegepaste wiskunde) en Jeff Westbrook (PhD in informatica), allen wiskundegeeks die het niet kunnen laten de Simpsons vol te proppen met al dan niet verborgen wiskundige concepten, grappen en puzzels. Elke maand lichten we in deze column zo’n wiskundig onderwerp nader toe vanuit de Simpsons

Complexiteitsklassen

We keren terug naar Homers driedimensionale avontuur in Treehouse of Horror VI (seizoen 7, aflevering 6). We kwamen daar al een bijna-tegenvoorbeeld voor de laatste stelling van Fermat tegen, en ook de formule van Euler (die een elegant verband geeft tussen de constanten e, π, i en 1) hangt in de lucht. Onze aandacht gaat dit keer uit naar een veel onschuldiger uitziende formule, die beweert dat P=NP. Als algebraïsche vergelijking is deze vlug gekraakt tot N=1 of P=0, maar de formule drukt eigenlijk een veel lastiger probleem uit de computerwetenschappen uit met betrekking tot complexiteitsklassen.

De klasse P staat voor beslissingsproblemen die een computer via een deterministisch algoritme kan oplossen in polynomiale tijd. Dit wil zeggen dat voor een invoerprobleem van grootte n, de oplossing moet kunnen worden gevonden in een tijd begrensd door een veelterm in n. Als vuistregel zegt men dat deze problemen ‘handelbaar’ blijven voor computers als de invoergrootte toeneemt. Enkele voorbeelden van problemen in deze klasse:

  • Zijn twee opgegeven gehele getallen onderling ondeelbaar? Dit kan efficiënt worden uitgerekend via het algoritme van Euclides, dat de grootste gemene deler bepaalt.
  • Bestaat er een route tussen twee opgegeven punten op een wegennet die korter is dan een opgegeven lengte? Het algoritme van Dijkstra levert een efficiënte methode om de kortste paden te bepalen.
  • Is een opgegeven getal een priemgetal? Dat dit probleem in P zit, werd pas in 2002 bewezen.

Een voorbeeld in contrast hiermee is het deelsomprobleem: gegeven een verzameling van gehele getallen, heeft die een deelverzameling die sommeert tot nul? Voor {–7, –3, –2, 5, 8} is het antwoord bevestigend want {–3, –2, 5} is zo’n deelverzameling. Wanneer de opgegeven verzamelingen groter worden, dan wordt het zelfs voor computers lastig om dit probleem op te lossen: er zijn in feite geen betere methodes bekend die het algemene probleem oplossen dan domweg alle mogelijke deelverzamelingen uitproberen, maar dit aantal neemt exponentieel toe (2n) in de lengte n van de opgegeven verzameling en wordt algauw veel te groot voor computers.

Een oplossing vinden is dus moeilijk, maar een potentiële oplossing controleren gaat natuurlijk wel heel vlot. Dit is het type van problemen die in de klasse NP zitten. Voor deze problemen moet een computer via een deterministisch algoritme een gegeven oplossing kunnen verifiëren. Merk op dat dit helemaal niets zegt over hoe we zo’n oplossing moeten vinden! Nog enkele NP-voorbeelden:

  • Het handelsreizigersprobleem: gegeven n steden en de onderlinge afstanden ertussen, bestaat er een route die alle steden aandoet en korter is dan een opgegeven lengte?
  • Heeft een opgegeven getal een niet-triviale deler kleiner dan een opgegeven waarde?
  • Gegeven een aantal werknemers met elk een eigen agenda, pas deze in een uurrooster in zodat er steeds voldoende werknemers aan het werk zijn, onder bepaalde arbeidsreglementen.
  • Gegeven een aantal dozen met een zekere capaciteit en een aantal objecten van verschillende massa, kunnen deze allemaal in de dozen verpakt worden zonder de capaciteit te overschrijden?

Ook bepaalde varianten en herformuleringen van puzzels zoals Sudoku of Mijnenveger zijn bewezen NP-problemen.

P versus NP

Het lijkt evident dat problemen in de klasse NP moeilijker zijn dan die in P. De (onwaarschijnlijke) uitspraak P=NP beweert echter dat beide klassen samenvallen, zodat een probleem waarvan een oplossing eenvoudig te controleren is, ook meteen eenvoudig op te lossen zou zijn. Dit heeft verstrekkende gevolgen: cryptografie en computerbeveiliging bijvoorbeeld steunen op het feit dat bepaalde problemen te moeilijk zijn om efficiënt op te lossen, en zouden niet langer veilig zijn als P=NP. Positief is dat veel praktische problemen zoals het handelsreizigersprobleem zouden haalbaar worden. Ook in computationele biologie, waar de analyse van DNA  of proteïnestructuren heel vaak blijkt uit te draaien op onhandelbare problemen, zou P=NP een grote vooruitgang betekenen. Zelfs op filosofisch vlak zijn de gevolgen frappant.

Desondanks is P=NP of P≠NP nog steeds een openstaand probleem, dat door het Clay Math Institute in 2000 werd opgenomen in de zeven Millennium Prize Problems. Wie waterdicht kan aantonen of weerleggen dat P=NP, wordt daarmee op slag wereldberoemd en krijgt daarvoor een prijs van maar liefst één miljoen dollar!

Deel dit artikel

Reageer op dit artikel
(bekijk de commentaren)