Wiskundemeisjes

Ionica & Jeanine
 
Slik Internetbureau Rotterdam Internetbureau Rotterdam



Categorieën

Archief

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

Homer

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)

1 reactie op “P-versus-NP”

  1. MD:

    In die aflevering stonden nog heel wat meer wiskundige verwijzingen, en een heleboel leuker zelfs dan "P=NP"! In die aflevering wordt een tegenbewijs van de stelling van fermat gegeven! Zie de afb. op mijn blog, die rekensom kan je zelf nagaan op je rekenmachientje.

    (o ja, die pdf is hier volledig onleesbaar!)

Plaats een reactie


Je kunt LaTeX gebruiken in je reactie.
Gelieve antwoorden op puzzels tussen [SPOILER] en [/SPOILER] te plaatsen.