Voor managers bestaan geen problemen, enkel uitdagingen. Wiskundigen zijn nog niet getroffen door de uitdagingziekte, zij worden nog altijd getroffen door problemen. Wat zijn de priemfactoren van 267 – 1? Hoe bepaalt een TomTom de snelste route tussen twee punten op een wegenkaart? Wat is de oplossing van een sudoku? Over dit soort problemen breken wiskundigen zich het hoofd, vooral sinds de komst van de computer. De problemen waarbij een computer, al dan niet binnen afzienbare tijd, een antwoord geeft, kunnen worden ingedeeld in twee categorieën: makkelijke problemen en moeilijke problemen. Wiskundigen spreken over P-problemen en NP-problemen, begrippen die verderop in dit artikel worden verklaard.
Euler- en Hamiltoncircuits
Een graaf is niets anders dan een verzameling punten (of knopen) en lijnen (of wegen, of takken) die de punten met elkaar verbinden. Een voorbeeld van een graaf zie je hiernaast. Kun je het plaatje natekenen zonder je potlood van het papier te halen, zonder lijnen meer dan één keer te tekenen en te eindigen in het punt waar je begon? Iets formeler geformuleerd: is het mogelijk om een wandeling in deze graaf te vinden waarbij elke lijn precies eenmaal doorlopen wordt en waarbij begin- en eindpunt hetzelfde zijn? Het antwoord op deze vraag kun je vinden door simpelweg alle mogelijke wandelingen na te lopen en te kijken of er een wandeling is die aan de gewenste voorwaarden voldoet. Er bestaat echter een slimmere manier. In 1736 toonde Leonhard Euler (1707-1783) aan dat de gevraagde wandeling (tegenwoordig Eulercircuit geheten) alleen dan bestaat als in elk punt van de graaf een even aantal lijnen samenkomt. Eulers redenering kwam hierop neer. Kom je tijdens de wandeling in een punt aan, dan moet je dat punt ook weer verlaten. Afhankelijk van het aantal keren dat je een punt aandoet, heb je dus 2, 4, 6, … lijnen nodig dat in zo’n punt samenkomt.
Bij de graaf hierboven komen in elk punt 4 lijnen samen. Op grond hiervan kunnen we dus concluderen dat de graaf een Eulercircuit bevat. Hoe zo’n circuit eruit ziet, is een andere vraag. Je kunt eenvoudigweg door proberen een Eulercircuit te vinden, of je kunt gebruikmaken van een algoritme, een systematische methode die stap voor stap tot de oplossing leidt. De Fransman M. Fleury publiceerde in 1883 een algoritme dat tot een Eulercircuit – mits zo’n circuit bestaat – leidt.
Beschouw opnieuw de graaf van het begin van dit artikel. Is het mogelijk een wandeling te maken waarbij elk punt precies eenmaal gepasseerd wordt en waarbij begin- en eindpunt hetzelfde zijn? Dit op het vorige lijkende probleem werd voor het eerst geformuleerd in 1858 door William Rowan Hamilton (1805-1865); een wandeling die aan de gestelde voorwaarden voldoet, heet daarom een Hamiltoncircuit. Opnieuw kunnen we de oplossing vinden door domweg alle wandelingen na te gaan. Maar ook hier zouden we liever een makkelijk trucje hebben om te beslissen of een Hamiltoncircuit al dan niet bestaat. Zo’n truc heeft tot op de dag van vandaag echter niemand kunnen vinden. Niemand weet een methode die je vertelt of een willekeurige graaf een Hamiltoncircuit bevat. De twee op het eerste gezicht zo op elkaar lijkende problemen, liggen in hun oplossing mijlenver uit elkaar: Hamilton’s versie is veel lastiger, omdat er bij dat probleem niks anders op zit dan alle mogelijkheden te verifiëren. Of zou een truc zoals bij Euler’s versie wel bestaan, maar is nog niemand op zo’n geniaal idee gekomen?
Sommige mensen denken dat het met nieuw te ontwikkelen oplossingstechnieken mogelijk moet zijn om een methode te vinden die je vertelt of een graaf wel of geen Hamiltoncircuit bevat. Vóór 1736 leek het Eulercircuit-probleem ook erg ingewikkeld, redeneren zij. De meeste wiskundigen en informatici geloven echter dat Hamilton’s versie echt moeilijker is dan Euler’s versie. Zij denken dat een snelle methode om te bepalen of een graaf een Hamiltoncircuit bevat, nooit zal worden gevonden – niet omdat we niet slim genoeg zijn om zo’n methode te vinden, maar omdat zo’n methode niet bestaat. Dat is echter niet meer dan een vermoeden, gebaseerd op ervaring en intuïtie; een bewijs ontbreekt!
Het criterium van de koffiepauze
Op vrijwel elke universiteit is de koffiekamer van de wiskundefaculteit een belangrijk ontmoetingscentrum. Op tafel ligt een pak kaarten, aan de muur hangt een schoolbord. Het is niet alleen een ruimte om te ontspannen, maar tevens een plek waar collega’s gedachten en ideeën over problemen uitwisselen. Ondertussen is de computer op de werkkamer bezig een berekening te voltooien.
Wiskundige Brian Hayes hanteert in zijn artikel ‘Accidental Algorithms’ het volgende criterium om de grens tussen snelle en langzame berekeningen te bepalen: een berekening is langzaam als deze nog niet is beëindigd als je terugkomt van een koffiepauze. De formele definitie luidt in termen van polynomiale tijd en exponentiële tijd algoritmen.
Vlotte en trage algoritmen
De computer kan een handig hulpmiddel zijn voor een wiskundige. Stel dat je computer bezig is met een berekening waarvan de input uit n getallen bestaat. De berekening kan het optellen van al deze getallen behelsen, of het bepalen van de grootste gemeenschappelijke deler, of het genereren van permutaties van deze getallen. Het doet er niet toe wat de precieze taak is, in alle gevallen zal de tijd die het programma nodig heeft om de berekening uit te voeren, afhangen van n, de lengte van de inputlijst (of preciezer: het totale aantal bits dat nodig is om deze n getallen op te schrijven). Hoe groter n, hoe langer de berekening zal duren. Misschien is de benodigde tijd bij n getallen evenredig met n2, dat wil zeggen: als n toeneemt van 10 tot 20 tot 30, neemt de benodigde rekentijd toe van 100 tot 400 tot 900. Als de rekentijd evenredig is met 2n en de input groeit van 10 tot 20 tot 30, neemt de rekentijd toe van 210 (ongeveer duizend) tot 220 (ongeveer een miljoen) tot 230 (ongeveer een miljard). De tijd is hierbij niet in seconden of iets dergelijks, maar meer een abstracte maat. Het is het best te interpreteren als het ‘aantal stappen’ dat het algoritme nodig heeft om tot het antwoord te komen.
Het aantal stappen kan relatief klein zijn, in welk geval het antwoord snel wordt gevonden, of groot, zodat de rekenpartij zo lang duurt dat je er maar beter niet aan kunt beginnen (ook een computer niet). De formele definitie van ‘snelle’ en ‘langzame’ algoritmen luidt in termen van polynomiale tijd en exponentiële tijd.
Functies van de vorm n → a⋅nc (hierbij zijn a en c positieve constanten) zijn polynomiale functies en n → c⋅an zijn exponentiële functies. Een polynomiale tijd algoritme is een algoritme waarvan de rekentijd evenredig is met een polynomiale functie, een exponentiële tijd algoritme is een algoritme waarvan de rekentijd evenredig is met een exponentiële tijd algoritme. Grofweg kun je zeggen dat een polynomiale tijd algoritme snel en efficiënt is. Een exponentiële tijd algoritme daarentegen is traag en daarom onpraktisch: als het honderden jaren duurt voordat de computer een antwoord geeft, hebben we er niks aan. In het onderstaande kader staat een voorbeeld van een berekening die in polynomiale tijd kan worden gedaan.
Determinanten
De determinant is een begrip uit de lineaire algebra. Het stelt een getal voor dat berekend wordt uit de elementen van een vierkante matrix. Je kunt er bijvoorbeeld mee vaststellen of een stelsel vergelijkingen een oplossing heeft. Wie de officiële recursieve definitie door middel van ‘ontwikkelen naar de eerste rij’ hanteert, overleeft het uitrekenen van een 25 × 25-determinant niet. De ontwikkelformule komt namelijk neer op het uitvoeren van veel meer dan n! vermenigvuldigingen en bij n = 25 wordt dat 25! ≈ 1,55 × 1025. Een computer die 1012 vermenigvuldigingen per seconde kan uitvoeren, doet daar zo’n 500.000 jaar over!
Door de matrix eerst op driehoeksvorm te brengen en dan de diagonaalelementen te vermenigvuldigen, wordt het werk gereduceerd tot n(n – 1) + (n – 1)(n – 2) + … + 2 × 1 + (n – 1). Bij n = 25 wordt dat 5224, een aanzienlijke tijdsbesparing! Concreet betekent het dat er 5224 stappen nodig zijn om de determinant te bepalen. Het uitrekenen van determinanten is iets dat in polynomiale tijd gedaan kan worden; de polynomiale functie die hoort bij het uitrekenen van de determinant van een n x n-matrix, is p(n) = n(n – 1) + (n – 1)(n – 2) + … + 2 × 1 + (n – 1) en die ligt in de orde van grootte van n3. Omdat p(n) een polynomiale functie is, zeggen we dat het uitrekenen van de determinant van een n x n-matrix een probleem uit de klasse P is.
De klassen P en NP
Voor een gegeven probleem kunnen verschillende algoritmen bestaan, de ene sneller dan de andere. In het kader over determinanten, hierboven, kun je lezen over twee verschillende algoritmen voor het uitrekenen van de determinant van een n x n-matrix, waarvan er één in polynomiale tijd kan worden uitgevoerd. De klasse van problemen die wiskundigen aanduiden met P zijn alle problemen die ten minste één polynomiale tijd algoritme hebben. Het algoritme moet het juiste antwoord geven in ten hoogste a⋅nc stappen (a en c zijn positieve constanten).
Van de meeste problemen waarvan we weten dat ze in polynomiale tijd kunnen worden opgelost, heeft het algoritme een exponent (de waarde van c in a⋅nc) van niet meer dan 4. Een probleem dat door een algoritme in, zeg, n100 stappen kan worden gekraakt, behoort weliswaar tot de klasse P (n → n100 is immers een polynomiale functie), maar komt men in de praktijk zelden tegen. De problemen waarvoor we geen polynomiale tijd algoritme kennen, kunnen – zolang we zo’n algoritme niet vinden – niet sneller worden opgelost dan in exponentiële tijd. Het zijn deze problemen waar het voor wiskundigen echt interessant wordt.
Het gaat om zogeheten ‘beslissingsproblemen’, problemen waarvan het antwoord ‘ja’ of ‘nee’ is. Voorbeelden zijn: ’Heeft deze graaf een Hamiltoncircuit?’ en ‘Is het getal 267 – 1 priem?’. Dit soort problemen hebben met elkaar gemeen dat áls je op goed geluk het antwoord raadt, of iemand jou het antwoord influistert, je de juistheid van dat antwoord snel kunt verifiëren. De klasse van dit soort problemen wordt aangeduid met NP. Preciezer geformuleerd: de verzameling NP is de verzameling van problemen waarbij de juistheid van een ‘ja’-antwoord (al dan niet gegeven in polynomiale tijd) geverifieerd kan worden in polynomiale tijd.
Voor NP-problemen doet het er niet toe hoeveel moeite het kost om een oplossing te vinden, het gaat er slechts om dat de gegeven oplossing efficiënt te verifiëren is. De letters NP staan voor nietdeterministisch polynomiaal. Grof gezegd betekent dit dat het algoritme oplossingen mag ’gokken’; een gegokte oplossing wordt daarna geverifieerd.
Het bestaan van een Hamiltoncircuit in een graaf is een voorbeeld van een NP-probleem. Hoewel er geen algoritme is dat vaststelt of een graaf een Hamiltoncircuit bevat, is het heel eenvoudig na te gaan of een aangereikte wandeling inderdaad alle punten precies eenmaal passeert en eindigt bij het beginpunt. De graaf hiernaast heeft inderdaad een Hamiltoncircuit, dit circuit is met blauwe lijnen weergegeven.
Overigens is de verificatie alleen te doen indien het antwoord ’ja’ is. Als je claimt dat een graaf géén Hamiltoncircuit bevat, zit er niks anders op dat daadwerkelijk alle wandelingen afzonderlijk te controleren. Dat geeft echter niet, want het leuke van NP-problemen is dat de ’nee’-antwoorden niet in polynomiale tijd bewijsbaar hoeven zijn.
Het Hamiltoncircuit-probleem kan worden gezien als een speciaal geval van het handelsreizigerprobleem, zie onderstaand kader.
Het handelsreizigersprobleem
Een handelsreiziger moet een bepaald aantal steden bezoeken en aan het eind weer terugkeren bij zijn vertrekpunt. Hij wil dat zo doen, dat elke stad precies één keer aan bod komt en bovendien moet de totaal af te leggen afstand zo klein mogelijk zijn. Tot op heden is er geen ideale oplossingsmethode gevonden voor dit Handelsreizigersprobleem. De handelsreiziger zou natuurlijk alle mogelijke circuits kunnen uitproberen, maar dat zijn er veel te veel: zelfs de snelste computers zouden daar miljarden jaren voor nodig hebben!
Daarom zijn er handige rekentrucs verzonnen waarbij niet alle mogelijkheden hoeven worden nagegaan. Met zo’n truc kon men in 1954 de kortste rondreis berekenen langs de toen nog 48 staatshoofdsteden in de VS. In 1980 berekende men een handelsreis langs 120 West-Duitse steden, inclusief Berlijn, en in 1987 een wereldreis langs 666 plaatsen verspreid over alle continenten, inclusief de Noord- en Zuidpool. Het huidige rekenrecord (uit 2004) voor het Handelsreizigersprobleem staat op 24.978 plaatsen, verdeeld over heel Zweden. De totale lengte daarbij is zo’n 72.500 kilometer en men heeft bewezen dat een korter circuit niet bestaat. In de figuur zie je deze route (in rood); klik op het plaatje voor een vergroting.
Een ander voorbeeld van een NP-probleem is ontbinding in priemfactoren. Een beroemde anekdote is een gebeurtenis tijdens een lezing van Frank Nelson Cole (1861-1926), die hij in 1903 hield bij een wiskundecongres. Zonder een woord te zeggen, liep hij naar het bord en schreef daarop: 267 – 1 = 147573952589676412927. Vervolgens schreef hij elders op het bord de getallen 761838257287 en 193707721 onder elkaar en berekende het product van deze twee getallen. Gedurende deze lange en nogal saaie exercitie sprak hij geen woord. Na veel schrijfwerk stond het antwoord op het bord: 147573952589676412927, hetzelfde als 267 – 1! Het publiek stond versteld; tot dan toe vermoedde men dat 267 – 1 een priemgetal was. Cole had zo-even laten zien dat dit vermoeden onjuist was. Niemand stelde Cole een vraag tijdens zijn ’lezing’, maar later vertelde hij dat hij er twintig jaar elke zondagmiddag aan had gewerkt om 267 – 1 te factorizeren. Dit voorbeeld maakt veel duidelijk: het kost ongelofelijk veel tijd om een groot getal te ontbinden in priemfactoren (het getal 267 – 1 gaat tegenwoordig heel snel op een computer, maar dat geldt niet voor getallen van een paar honderd cijfers), maar als iemand je de priemfactoren vertelt, kun je makkelijk de juistheid verifiëren.
De verzameling NP is enorm groot: het bevat duizenden problemen, niet alleen zuiver wiskundig van aard, maar ook in vakgebieden als de kunstmatige intelligentie, natuurkunde, biologie en economie. De verzameling P is een deelverzameling van NP. Alle P-problemen voldoen immers ook aan de definitie van een NP-probleem: een probleem waarvoor een polynomiale tijd algoritme bestaat, is zeker in polynomiale tijd geverifieerd. Het interessante aan NP is dat er ook veel problemen toe behoren waarvan we niet weten of ze in P bevat zijn. Zou het zelfs zo kunnen zijn dat voor alle NP-problemen efficiënte algoritmen bestaan (en dus tot de klasse P behoren), maar dat we deze algoritmen simpelweg nog niet hebben gevonden? Dat is de centrale vraag van het P versus NP probleem.
De klasse NP-volledig
Binnen de klasse NP bevindt zich een elitegroep van problemen die NP-volledig wordt genoemd. Deze NP-volledige problemen hebben een extra eigenschap: als één van deze problemen in polynomiale tijd kan worden opgelost (en dus tot de klasse P behoort), dan kunnen alle NP-problemen (zowel de NP-volledige als de overige NP-problemen) met diezelfde methode in polynomiale tijd worden opgelost. Met andere woorden, als een dergelijk algoritme wordt gevonden, dan impliceert dat dat P = NP: de (ogenschijnlijk) moeilijke problemen zouden zich niet onderscheiden van de makkelijke problemen!
Zoiets raadselachtigs kom je maar zelden tegen. Hoe kun je voor honderd procent zeker zijn dat een oplossing voor één bepaald probleem werkt bij al die andere, duizenden, NP-problemen? Dit resultaat wordt nog verbijsterender als je bedenkt dat je niet eens weet wat al die NP-problemen zijn. Het eerder genoemde Hamiltoncircuit-probleem is NP-volledig. Een ander voorbeeld van een NP-volledig probleem is het deelsomprobleem, zie onderstaand kader.
Het deelsomprobleem
Een bekend voorbeeld van een NP-volledig probleem is het deelsomprobleem. Stel we hebben 100 getallen van drie cijfers. Bestaat er een deelverzameling waarvan de som van de elementen gelijk is aan 10.000? Ondanks alle wiskundekennis van tegenwoordig is er voor de oplossing van dit probleem weinig beters bekend dan dat we alle mogelijke deelverzamelingen uitproberen. Dit zijn dus 2100 (ongeveer 1030) pogingen die we moeten uitvoeren. Als iemand er na vele dagen of jaren achter komt dat er inderdaad zo’n deelverzameling bestaat, dan is er een heel eenvoudige manier om anderen daarvan te overtuigen. Geef die ander gewoon de getallen uit de bewuste verzameling en laat hem verifiëren dat hun som inderdaad 10.000 is. Dit bewijs van de juistheid van het ‘ja’-antwoord kan in zeer korte tijd uitgevoerd worden, maar het daadwerkelijk vinden van dit bewijs is daarentegen een heel ander verhaal. In de definitie van NP gaat het ons echter alleen om het bestaan van een polynomiaal bewijs, er wordt niets gezegd over de moeite die men nodig had om eraan te komen.
De ongelofelijke ontdekking dat alle NP-problemen makkelijk zouden kunnen zijn, namelijk als er voor één NP-volledig probleem een polynomiale tijd algoritme wordt gevonden, werd in 1971 gedaan door Stephen A. Cook (1939). Als we ooit een polynomiale tijd algoritme voor het Hamiltoncircuit-probleem vinden, zijn in één klap alle NP-problemen polynomiaal oplosbaar, inclusief ontbinding in priemfactoren (wel NP, maar niet NP-volledig). In de paar jaar volgend op Cook’s ontdekking breidde de lijst van NP-volledige problemen zich uit tot enkele honderden en inmiddels weten we al van een paar duizend problemen dat ze NP-volledig zijn.
In het oorspronkelijk werk van Cook wordt niet het Hamiltoncircuit-probleem genoemd, maar het Satisfiability problem voor logische uitdrukkingen. Vlak daarna ontdekte Richard M. Karp (1935) dat het Satisfiability problem polynomiaal kan worden teruggevoerd tot diverse andere problemen in de klasse NP-volledig, zoals het Hamiltoncircuit-probleem en het deelsomprobleem. Cook ontving in 1982 de Turing Award – gezien als de Nobelprijs voor informatica – voor zijn werk aan het P versus NP probleem. Karp ontving deze prestigieuze prijs drie jaar later.
Diverse geniale breinen hebben geprobeerd een polynomiale tijd algoritme te vinden voor een NP-volledig probleem. Omdat dit tot nu toe niet succesvol is gebleken, zijn velen daardoor gesterkt in de mening dat zo’n algoritme niet bestaat. Dit impliceert automatisch het vermoeden dat P ≠ NP. Inderdaad, het idee dat alle NP-problemen ’makkelijk’ zouden zijn, dus dat P = NP, klinkt te mooi om waar te zijn. Maar ook P ≠ NP is een wonderbaarlijke uitspraak: het betekent dat van alle NP-volledige problemen (dat zijn er duizenden!) er niet één oplosbaar is in polynomiale tijd.
Nog enkele NP-problemen
- Optimale Golomb-linialen
- Sudoku’s (pdf)
- Tetris
- Mijnenvegen (Eng.)
Op de P versus NP page van de Technische Universiteit Eindhoven worden vermeende bewijzen van ofwel P = NP ofwel P ≠ NP verzameld. Al die bewijzen worden nauwkeurig gecontroleerd door specialisten. Tot nu toe blijkt geen enkel bewijs waterdicht. Het hardnekkige voortbestaan van het P versus NP probleem en het grote belang ervan voor computationele toepassingen hebben ervoor gezorgd dat het een plaats heeft gekregen onder de bekendste problemen in de wiskunde. In 2000 kwam het probleem op de lijst van zeven grootste open problemen uit de wiskunde: de millennium problems van het Clay Mathematics Institute. Voor de persoon die in staat is om zo’n probleem te kraken, ligt een miljoen dollar klaar.
Gebruikte literatuur
- Brian Hayes, ‘Accidental Algorithms’ (pdf, Eng.)
- F. Beukers, ‘P = NP?’, Vakantiecursus CWI 1999 (pdf)