WW: P is (niet) NP?

De woensdagmiddag is op GeenCommentaar Wondere Woensdagmiddag. Met extra aandacht voor de nieuwste ontwikkelingen in Wetenschap- en Techniekland.

Net zoals in de topsport zijn er ook in de wetenschap topprijzen voor zeer bijzondere prestaties. Zo is daar bijvoorbeeld de Ansari X-prize voor het eerste particulier ontwikkelde ruimtevaartuig en zijn er vervolg-X-prizes op het gebied van exploratie, energie, scholing en bio-wetenschappen. In de wiskunde zijn er sinds 2000 de Millennium Prize Problems, bijgehouden door het Clay Mathematics Institute in Massachusetts. Een correcte oplossing voor één van deze zeven problemen levert 1.000.000 Amerikaanse dollars op. Genoeg aanleiding dus om een puzzelpoging te wagen.

Eén van de zeven problemen, het bewijzen van het Vermoeden van Poincaré werd in 2003 opgelost door middel van een bewijs van Grigori Perelman, die tot op heden de prijs weigert. Nu lijkt er ook voor een ander Milleniumprobleem een oplossing aangedragen te zijn. Dit keer voor het zogenaamde P != NP (spreek uit P is niet NP) probleem. Dit wiskundige probleem is ook één van de grote open vragen uit de theoretische informatica en als zodanig is een oplossing potentieel ook praktisch interessant.

Allereerst maar eens de uitleg over het probleem: Het gaat hier om de complexiteit van rekenkundige problemen. Sommige problemen zijn moeilijker dan andere en wiskundigen hebben klassen van moeilijkheid vastgesteld. “P” problemen zijn “makkelijk” en “NP” Problemen zijn “moeilijk”.

Complexiteit van een probleem kan uitgedrukt worden in de tijd die het kost om tot een oplossing te komen als je alle mogelijkheden probeert net zolang totdat je de goede oplossing vindt. Problemen die “P” zijn, zijn in redelijke tijd op te lossen, dat wil zeggen dat als je meer ‘puzzelstukjes’ toevoegt, de tijd die je nodig gaat hebben om het op te lossen hoogstens polynomiaal (bijvoorbeeld kwadratisch) verhoogt. Een voorbeeld is het bepalen of een getal een priemgetal is of het vinden van de grootste gemene deler, allemaal problemen die in afzienbare tijd opgelost kunnen worden, min of meer onafhankelijk van hoe groot de het getal is waarmee je begint.

NP zijn veel lastiger, daarvan wordt het aantal mogelijkheden dat je moet bekijken sneller dan polynomiaal groter. Maar ze zijn wel zo makkelijk dat als je een oplossing denkt te hebben, je relatief snel kan checken of deze klopt.

Nu is al tijden de vraag of deze klassen problemen wel inderdaad gescheiden zijn. Met andere woorden, is er een fundamenteel verschil tussen moeilijke en makkelijke problemen. Of nog anders geformuleerd:

Is er een wezenlijk verschil tussen het herkennen van een goede oplossing en het zelf produceren van zo’n oplossing voor een willekeurig probleem.

Of zoals Scott Aaronson van MIT zei: [Als P=NP het geval is:]

Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss…

Om deze en andere redenen vermoedden de meeste wiskundigen dat P inderdaad niet gelijk is aan NP. Maar alleen een ‘echt’ bewijs telt. En dat lijkt nu aangedragen te zijn door een wetenschappelijk medewerker van HP, Vinay Deolalikar. In een artikel van 102 pagina’s geeft hij naar eigen zeggen het bewijs dat P niet gelijk is aan NP. Op Twitter en Facebook (in bepaalde kringen) gonst het al dagen over dit bewijs. Het bewijs moet nog uitentreure gecontroleerd worden, dat zal dus nog wel even duren. Maar als dit bewijs steek houdt dan zet Deolalikar de theoretische informatica weliswaar niet op z’n kop, maar kan iedereen wel eindelijk vredig slapen.