Meest sexy computerprobleem P versus NP is weer ‘opgelost’

Uit de krochten van computerblogs komt -alweer- een oplossing  opborrelen van het ondoorgrondelijke P versus NP probleem, een van de fundamentele computerwetenschappelijke problemen en door tijdschrift Nature ooit omschreven als het meest sexy van alle.

Een Russische geleerde heeft tien jaar van zijn werkzame leven besteed aan de breinkraker rond een P versus NP probleem, het zogeheten 3-SAT probleem (wiki). Hiermee zou in theorie de veronderstelde tegenstelling P versus NP op de helling gaan. Say what?

Het NP versus P probleem is als volgt te omschrijven: 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? NRC-wetenschapsredacteur Margriet van der Heijden gebruikte al eens de volgende analogie:

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.

De uitdaging is om het bewijs te leveren dat de schier onmogelijk op te lossen problemen waarvan de oplossing eenvoudig te verifiëren is (NP) inderdaad gelijk zijn aan de problemen die wel binnen polynomiale tijd (zeg maar: afzienbare tijd) op te lossen zijn, de zogeheten P-problemen. Vorig jaar kwam een Amerikaanse wetenschapper met het bewijs dat P juist niet gelijk aan NP is. Dat bewijs is omstreden.

In potentie zou de theoretische gelijkstelling van P aan NP verstrekkende gevolgen kunnen hebben voor versleutelingstechnieken waar bijvoorbeeld Robert M. maar ook Wikileaks en uw bank gebruik van maken. Immers, het vinden van de sleutel zou niet meer oneindig lang duren. Zo ver is het (nog) lang niet. Wat wel bijzonder is aan de recente oplossing is dat de Rus, Vladimir Romanov, zijn bewijs geïmplementeerd heeft in computercode. Het wachten is nu op het weerleggen van zijn bewijs.

Eigenlijk is er maar een zaak klip en klaar als het gaat om P versus NP: