#WiskundePlantyn

26 jaar lang verbeteren

In het jaar 2000 gaf het Clay Mathematics Institute of Cambridge een lijstje met zeven millenniumvragen vrij. De oplossing van elke afzonderlijke vraag is één miljoen dollar waard. Het feit dat na vijftien jaar slechts één vraag is opgelost, geeft je al een idee van de moeilijkheidsgraad van de zeven uitdagingen. Vanwege het hoge niveau is het ook voor degenen die de oplossing moeten nakijken steeds een hele klus.

Veertien jaar voor de lijst werd vrijgegeven had een man een bewijs ingediend met een oplossing van het zgn. Handelsreizigersprobleem. Dat kwam niet aan bod op de lijst, maar indien zijn werk correct bleek te zijn, zou het ook een oplossing van het P-versus-NP-probleem impliceren, wat wél een milleniumvraag is.

Pas 26 jaar later slaagde een team van onderzoekers erin zijn poging definitief te ontkrachten. Bij de onderzoekers waren mensen van het CWI (Centrum Wiskunde & Informatica) in Amsterdam, de Vrije Universiteit Brussel en de Friedrich-Alexander-Universität in Erlangen-Nürnberg.
Het P-versus-NP-probleem stelt zich de volgende vraag: ‘Zijn problemen waarvan het antwoord snel met een computer te controleren zijn (P-problemen) ook altijd snel op te lossen met een computer (NP-problemen)?’

Meer weetjes?

Deel dit artikel

Reageer op dit artikel
(bekijk de commentaren)