Internetbureau Rotterdam 
Dit bericht is geplaatst op vrijdag 9 maart 2007 om 12:25 in categorieën Algemeen. Je kunt de reacties volgen via een RSS 2.0 feed. Je kunt een reactie plaatsen, of een trackback van je eigen site plaatsen.
Wiskundemeisjes
Ionica & Jeanine
P-versus-NP
In Algemeen, door wiskundemeisjes
Stefan wees ons in een reactie op de geweldige pagina P-versus-NP. P en NP zijn de namen van twee klassen problemen en het is een open vraag of deze klassen hetzelfde zijn. Heel kort door de bocht zijn P-problemen makkelijk op te lossen en is voor NP-problemen de oplossing makkelijk te controleren. De vraag is of P gelijk is aan NP, ofwel: is elk probleem waarvan de oplossing makkelijk te controleren is, ook makkelijk op te lossen? Het Clay Mathematics Institute loofde in 2000 een miljoen dollar uit voor een antwoord op deze vraag. Op de pagina P-versus-NP worden `bewijzen' verzameld.
Homer Simpson belandde trouwens een keer in een wereld waar het probleem was opgelost...
Het mooiste op de P-versus-NP pagina vond ik een enquete die William Gasarch onder deskundigen hield. Hij vroeg aan deskundigen wat zij dachten over P versus NP. Wanneer zou het probleem opgelost worden? Met welke technieken? En denken ze zelf dat P gelijk is aan NP of niet?
Honderd mensen reageerden en de meerderheid gelooft dat de vraag uiteindelijk opgelost zal worden en dat P niet gelijk is aan NP. Ik vond het erg leuk om de reacties te lezen. Verschillende grote namen geloven bijvoorbeeld dat P wel gelijk is aan NP. Zoals Donald Knuth die voorspelt dat dit in 2048 of 4096 bewezen zal worden.
Dana Nau grapt dat hij een prachtig bewijs heeft dat P ongelijk is aan NP, maar dat het helaas niet in de marge van de email past.
Mijn favoriete reactie komt van Michael Sipser: As you may know, when I was a graduate student in the mid 1970s I predicted that it would be solved by the century’s end. I also bet Len Adleman an ounce of gold that I would be right. Now that I’ve paid off, I’m more reluctant to make a prediction once again. But I’ll go out on a limb and give it another 25 years, so by around 2025. And I’ll stick with my earlier prediction that the resolution will be a proof that P is not equal to NP. The technique would be combinatorial, but that isn’t saying much. No more bets, however.
Lees zelf de hele enquete in deze pdf.
(Ionica)
