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.
Aardig dat fundamentele wiskunde onder de aandacht wordt gebracht. Ik begrijp alleen niet hoe de auteur kan stellen: “dat [bewijs] lijkt nu aangedragen te zijn”.
Er is een wiskundige die een artikel op zijn eigen website heeft gezet. Gewone stervelingen als u en ik kunnen dat artikel niet begrijpen, en experts alleen wanneer ze er echt voor gaan zitten. Er is nog geen [i]peer review[/i] geweest.
In hetzelfde “gegons” is al veel verwezen naar [url=http://www.win.tue.nl/~gwoegi/P-versus-NP.htm]deze pagina van de TU/e[/url] waar alle pogingen tot een bewijs voor P = NP dan wel P!=NP tot nu toe zijn verzameld. Voorlopige conclusie: geen bewijs. Voorts worden er in diezelfde blogkringen nu al [url=http://science.slashdot.org/story/10/08/11/0239209/Possible-Issues-With-the-P--NP-Proof]bezwaren tegen de huidige opgeworpen[/url].
Ik hoop dat de afleiding correct is, danwel nieuwe inzichten bevat die ons vooruit kunnen helpen. Maar vooralsnog betracht men liever terughoudendheid, in plaats van de zoveelste hype te ondersteunen.
Goed punt Baron E, het gaat hier voorlopig nog om een nog-niet-gepeerreviewd bewijs en skepsis past dus inderdaad. Toch leek het me aardig eens in een vroeg stadium de aandacht te vestigen op hoe dit soort wiskundige bewijzen voor fundamentele vraagstukken nog steeds opduiken. Ook laat het zien (vooral in combinatie met je tweede link) dat er wel degelijk discussie is over dit soort vraagstukken. Spannend dat we daar nu middenin zitten.
Dat gezegd hebbende, je twee links zijn zeer welkome aanvullingen op dit stukje. Dankjewel!
Ik heb trouwens de eerste paar pagina’s van het bewijs doorgelezen maar mijn expertise kent toch zijn grenzen :)
http://www.newscientist.com/article/dn19313-tide-turns-against-milliondollar-maths-proof.html