QR-codeGerenommeerd natuurwetenschappelijk tijdschrift Nature noemde het the sexiest problem in computer science. Nederlandse kranten schreven er uitgebreid over. P versus NP, één van de zeven Millennium Prize Problems waarvoor een miljoen dollar was uitgeloofd, zou zijn opgelost. Begin augustus publiceerde Vinay Deolalikar, informaticus, een wiskundig bewijs. Maar, zo schreven de kranten, het viel nog maar te bezien of het bewijs wel correct was. Vakgenoten waren het er niet over eens. Hoe kan dat? De kracht van de wiskunde is toch juist dat een bewijs objectief juist of onjuist is?

Het probleem P versus NP

Soms is het niet alleen interessant om te weten hoe je een vraagstuk oplost, maar ook hoe lang het duurt om het op te lossen. En daar draait het om bij the sexiest problem in computer science. Vraagstukken worden ingedeeld in verschillende categorieën, gebaseerd op hoe snel of langzaam een computer ze zou oplossen. Twee van zulke categorieën zijn P en NP. Een sudoku is bijvoorbeeld een NP-vraagstuk, en bepalen of een getal priem is (alleen deelbaar door zichzelf en 1) een P-vraagstuk.

Het verschil tussen P en NP zit ‘m in het type computer dat er aan te pas komt: de vraagstukken in P zijn allemaal vrij snel oplosbaar voor een gewone computer. De vraagstukken in NP zijn (in theorie) snel oplosbaar voor een computer die niet één voor één alle mogelijkheden doorrekent, maar ineens kan gokken. Informatici denken dat zo’n gokkende computer fundamenteel anders is, en moeilijke problemen sneller kan oplossen. Maar zonder bewijs is dat niet zeker: misschien kan een gewone computer het gok-element wel nabootsen. In dat geval zouden P en NP eigenlijk precies dezelfde problemen omvatten. De grote vraag is nu: zijn P en NP gelijk of ongelijk?

Deolalikars bewijs

In augustus claimde Deolalikar te hebben bewezen dat P en NP ongelijk zijn. Al gauw werd er op internet volop gediscussieerd over de vraag of dit bewijs correct was. Idealiter zou een bewijs natuurlijk objectief ‘goed’ of ‘fout’ moeten zijn, en zou zo’n discussie niet nodig zijn. Maar idealiter zou een bewijs ook uit een soort stappenplan moeten bestaan waarbij iedere stap onomstotelijk uit de vorige volgt. Daar zijn in de wiskunde heel formele methodes voor. Echter, een bewijs volgens zo’n formele methode is belachelijk gedetailleerd, en daardoor langdradig en moeilijk leesbaar.

Om langdradigheid te voorkomen laten wiskundigen voor de hand liggende bewijsstappen weg. Ze zeggen dan dat die “triviaal” zijn, of “overduidelijk”. Wat ze bedoelen, is dat een specialistische lezer die stappen redelijk makkelijk zelf zou kunnen bedenken. Zolang die lezers die weggelaten stappen inderdaad zelf kunnen invullen, zullen die het bewijs als correct accepteren. Een wiskundig bewijs leveren draait in de praktijk dus vooral om voldoende stappen uitwerken zodat je je lezers overtuigt. Maar Deolalikars overtuigde zijn collega’s niet met zijn bewijs.

En nu?

Deolalikar is naar aanleiding van de kritiek nog eens gaan sleutelen aan zijn bewijs. Op zijn website staat dat het bewijs volgens hem nu ‘gerepareerd’ is: hij heeft de bewijsstappen verder uitgewerkt, en is daarbij geen fouten tegengekomen. De volgende fase is een controle door vakgenoten bij een wiskundig tijdschrift. Blijkt Deolalikars bewijs correct, dan krijgt hij de prijs van een miljoen dollar die voor de oplossing van dit probleem was uitgeloofd. En heeft hij voor altijd the sexiest problem in computer science op zijn naam staan.