De oplossing van het onoplosbare

Het is opgelost: het grootste en mooiste probleem uit de computerwetenschap. Dat zegt een onderzoeker. In zijn bewijs zitten nog veel gaten, zeggen anderen.

De website van Nature spreekt van het sexiest problem in de computerwetenschap. De Clay Foundation loofde een miljoen dollar uit voor de oplossing. En nu claimt Vinay Deolalikar, senior-onderzoeker bij HP Labs in Palo Alto dat hij die oplossing heeft gevonden.

Op 6 augustus stuurde Deolalikar een select groepje wiskundigen en computerwetenschappers een lang manuscript. Daarin gaf hij antwoord op de beroemde vraag die Stephen Cooke en Leonid Levin in 1971 onafhankelijk van elkaar formuleerden. Kort gezegd: als je makkelijk kunt controleren of de oplossing van een probleem juist is, zou je die oplossing dan in principe ook makkelijk moeten kunnen vinden?

Nee, concludeert Deolalikar na 102 pagina’s waarin hij uiteenlopende takken van wiskunde en computerwetenschappen bij elkaar brengt. En daarmee verbaasde hij collega’s, want zij dachten dat deze eenvoudige vraag nagenoeg onmogelijk te beantwoorden was.

Een populaire metafoor voor het probleem is die van de legpuzzel, zeg eentje met duizend stukjes. Of die allemaal juist aan elkaar zijn gepast zie je in één oogopslag. Maar de puzzel maken vergt stukken meer tijd. En zoiets geldt ook voor veel zogeheten NP-problemen uit de wiskunde. De cryptografie is erop gebaseerd: als je de geheime sleutel krijgt, zie je direct of hij de code breekt. Maar die sleutel zelf vinden is (als het goed is) onbegonnen werk.

Net zo herken je snel de kortste weg die een handelsreiziger kan nemen als hij dertig steden allemaal één keer wil aandoen en daarna thuis wil aankomen. Maar die kortste weg zomaar vinden..., ook daarvoor bestaat nog altijd geen optimale methode. En zo zijn er duizenden NP-problemen geformuleerd.

Bestaat er misschien toch een makkelijke (een ‘P’) oplossing voor, is nu de vraag. En het wonderlijkste is misschien dat die vraag zo algemeen geldt. Dat zit zo: er bestaat een groep speciale NP-problemen - ‘NP-volledige problemen’. En als je van één zo’n speciaal NP-probleem aantoont dat het efficiënt op te lossen is (dat het ‘P ’ is) dan heb je in één klap aangetoond dat alle NP-problemen efficiënt op te lossen zijn ( ‘P’ zijn).

Anders gezegd: een creatieve oplossing van een ingewikkeld probleem zou dan altijd te vervangen zijn door een efficiënt formalisme. Scott Aaronson, computerwetenschapper aan het MIT, vergeleek het met componeren. “Als P gelijk is aan NP”, zei hij, “dan zou iedereen die een symfonie herkent ook een Mozart zijn [...].”

Het omgekeerde – P is niet gelijk aan NP, zoals Deolalikar zegt te hebben bewezen – zou veel wiskundigen trouwens evenzeer verbazen. Géén enkel complex NP-probleem zou dan wezenlijk te versimpelen zijn!

Of Deolalikar dat echt heeft aangetoond, is intussen onzeker. Aaronson hoort bij de groeiende groep wetenschappers die denken dat het bewijs niet klopt. Na een snelle blik erop verwedde hij er, via zijn blog, zelfs zijn huis om.

Andere wiskundigen en computerwetenschappers, waaronder de bekende Fieldsmedaille-winnaar Terence Tao, pakten het serieuzer aan. Zij lieten alles uit handen vallen om het bewijs te controleren, en openden zelfs speciale Wiki-pagina’s. Dick Lipton, hoogleraar computerwetenschap aan Georgia Tech, beschreef de afgelopen tien dagen in zijn blog hoe deze groep steeds meer gaten in het bewijs schoot.

Wat vindt Deolalikar van deze (openbare) activiteit? Hij verwijst naar de verklaring op zijn website: “Met de eerste voorlopige versie van het bewijs wilde ik alleen een beperkt aantal onderzoekers om commentaar vragen, naar goed gebruik. [...] Ik heb al de kwesties die rond de voorlopige versie zijn opgeworpen opgelost [...] Het herziene manuscript heb ik naar een klein aantal onderzoekers gestuurd.”

Lipton hoorde daar niet bij, mailt deze desgevraagd. Maar: “[...] Hij houdt vol dat hij een bewijs heeft, dus ik veronderstel dat er nog kans is op een oplossing.” Erg groot is die kans volgens de meeste wiskundigen echter niet. Aaronson heeft zijn huis al tot 2019 verwed. Het is geen grapje, licht hij in zijn blog toe, als we zeggen dat dit probleem alleen is op te lossen met een immense sprong in menselijke kennis.