Pieter Edelman
14 September 2017

Een claim van een Duitse wiskundige rond de vraag of P gelijk is aan NP zorgde deze zomer voor de nodige beroering. Het bleek een storm in een glas water.

Een mild relletje stak afgelopen komkommerseizoen de kop op in programmeurskringen: Norbert Blum van de universiteit van Bonn claimde een antwoord te hebben gevonden op de roemruchte vraag ‘is P gelijk aan NP?’. Na kritiek trok hij die claim tweeënhalve week later weer in.

Op zichzelf is zo’n claim niet zo bijzonder – dergelijke beweringen duiken regelmaat van de klok op. Het bijzondere is dat het nu een wiskundige van statuur is die met de claim komt.

De P-vs-NP-vraag houdt de gemoederen binnen de informatietheorie al decennia bezig en is een van de zeven Millennium Prize-problemen, waarvan het Clay Mathematics Institute in 2000 een miljoen dollar uitloofde voor de oplossing. Het heeft te maken met de moeite die het kost om een oplossing te vinden voor een probleem. De algemene aanname, dat P niet gelijk is aan NP, stelt dat er problemen zijn waarvan de uitkomst wel relatief eenvoudig te checken is, maar niet eenvoudig te berekenen.

Het schoolvoorbeeld is ontbinden in priemfactoren. Er is geen manier bekend om te beredeneren welke twee priemgetallen met elkaar vermenigvuldigd moeten worden om een specifieke uitkomst te krijgen; ze moeten domweg allemaal worden uitgeprobeerd. Maar om te controleren of de twee factoren het gewenste getal vormen, is slechts een enkele vermenigvuldiging nodig.

Dit probleem is typisch NP, wat staat voor ‘niet-deterministisch polynomiaal’. ‘Polynomiaal’ heeft betrekking op de afhankelijkheid tussen de grootte van de input en het aantal benodigde stappen om het probleem op te lossen, of anders gezegd: hoe snel de rekentijd groeit met de grootte van het probleem. Polynomiaal kan worden geïnterpreteerd als ‘behapbaar’, tegenover bijvoorbeeld een exponentieel probleem; het aantal stappen kan met een macht toenemen, maar explodeert niet volledig.

P-problemen zijn allemaal NP-problemen – hun oplossing is altijd ‘makkelijk’ te controleren. Maar ze hebben als speciale eigenschap dat ook de berekening in polynomiale tijd te doen is. Het is echter nooit aangetoond dat P een subset is van NP; het zou kunnen dat de twee volledig gelijk zijn. Met andere woorden: dat P = NP, ofwel: dat alle problemen die in polynomiale tijd te checken zijn ook in polynomiale tijd te berekenen zijn.

Dat zou forse consequenties hebben. Cryptografie zoals we die nu kennen, zou onbruikbaar worden. Maar allerlei vraagstukken binnen de wetenschap, variërend van biologie tot logistiek, zouden makkelijker zijn op te lossen.

Sudoku
Illustratie: Istock/Thinkstock

Wrevel

Blum beargumenteerde in een niet-gepeerreviewd paper op Arxiv dat, volgens verwachting, P ongelijk is aan NP – de twee klassen verschillen inderdaad fundamenteel van elkaar. De reactie van de wiskundigen was aanvankelijk voorzichtig: Blum is een gerespecteerd mathematicus en het paper zit volgens hen goed in elkaar. Maar tegelijk is het wel een stoutmoedige claim: bewijzen blijken keer op keer niet stand te houden.

Al snel werden er dan ook lekken ontdekt, die uiteindelijk groot genoeg bleken om het hele bewijs onderuit te halen. Eind augustus moest Blum toegeven dat zijn bewijs niet klopt. Hij zal nog uit de doeken doen wat er precies mis is, maar daar is hij op het moment van schrijven nog niet aan toegekomen.

Ophef om niks dus, of gewoon wetenschap aan het werk? Stellingen poneren en kritiek verzamelen van collega’s is een van de fundamenten van de wetenschap, maar het moet gezegd dat Blum het niet heel handig heeft aangepakt. In plaats van direct contact te zoeken met collega’s of een blogpost te schrijven om zijn ideeën te bespreken, slingerde hij een volledig uitgewerkt paper de wereld in dat niet de air had van een discussiestuk.

Dat wekte de nodige wrevel binnen de gemeenschap. Scott Aaronson, hoogleraar aan de universiteit van Austin in Texas, ging zelfs zover om een website haspvsnpbeensolved.com in te stellen. De site ‘analyseert’ een geüpload paper en geeft vervolgens altijd hetzelfde antwoord: nee.

Die ophef is zonde, want de echte vraag is of Blums werk nieuwe inzichten biedt die beantwoording van de vraag dichterbij brengen. Op die analyse moeten we nog even wachten.