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”.