Wiskundemeisjes

Bewijs voor P != NP ???

Brekend nieuws: Wiskundige Vinay Deolalikar heeft een voorlopige versie verspreid van een artikel dat claimt te bewijzen dat P != NP. Deolalikar is een serieuze onderzoeker en had het bewijs alleen bedoeld voor een handvol deskundigen. Hij werkt nog aan een definitieve versie, maar zijn eerste versie circuleert nu al op internet. Ik heb vandaag weinig tijd om erover te schrijven, maar dit nieuws kan natuurlijk niet onvermeld blijven!

Voor niet-wiskundigen: lees op Kennislink wat P- en NP-problemen zijn.

Voor wiskundigen: bekijk zelf het bewijs of volg de discussie op Dick Liptons blog.

8 reacties op “Bewijs voor P != NP ???”

1. Arjan:
   maandag 9 augustus 2010 om 14:00

   Spannend! Ik hou deze site in de gaten voor nieuws...

2. Taco:
   dinsdag 10 augustus 2010 om 02:22

   Spannend!!

3. Loy:
   woensdag 11 augustus 2010 om 12:24

   Dus, kort samengevat: van een oplossing van een moeilijk probleem (Zie kennislink), dus bijv. een route in het handelsreizigersprobleem, is het dus niet makkelijk te bewijzen dat die oplossing klopt?

4. Frans:
   woensdag 11 augustus 2010 om 14:00

   Je kan aan het aantal reacties zien dat er bij deze post NIETS te halen valt (zoals een gratis boek).

   Ach het is maar het P=NP probleem. Een van de fundamentele vragen in de wiskunde, informatica, biologie en natuurkunde.

   Op IAS is een video (voor beginner) van Avi Wigderson
   http://video.ias.edu/P-vs-NP

   Zo!

   Ik ga vlug naar de andere post zodat ik ook kans kan maken op een gratis boek.

5. Geertje:
   woensdag 11 augustus 2010 om 22:37

   Hier nog een reactie, al was het maar om Frans te laten merken dat er toch echt wel meer mensen zijn die dit nieuws geweldig vinden. Inderdaad, spannend!

6. Michel:
   woensdag 11 augustus 2010 om 23:11

   Loy: Nee. Het blijft makkelijk te bewijzen dat de oplossing klopt. Alle NP problemen zijn gedefinieerd door de eigenschap dat het verifiëren van een oplossing in P-tijd kan. Het vinden van een oplossing blijft de moeilijkheid, niet het verifiëren.

7. Ionica:
   donderdag 12 augustus 2010 om 09:58

   Na een paar hectische dagen vol uitgebreide discussies op internet vat Terence Tao de situatie alsvolgt samen (in een reactie bij Dick Lipton).

   
   I think there are several levels to the basic question “Is the proof correct?”:

   1. Does Deolalikar’s proof, after only minor changes, give a proof that P != NP?

   2. Does Deolalikar’s proof, after major changes, give a proof that P != NP?

   3. Does the general proof strategy of Deolalikar (exploiting independence properties in random k-SAT or similar structures) have any hope at all of establishing non-trivial complexity separation results?

   After all the collective efforts seen here and elsewhere, it now appears (though it is perhaps still not absolutely definitive) that the answer to #1 is “No” (as seen for instance in the issues documented in the wiki), and the best answer to #2 we currently have is “Probably not, unless substantial new ideas are added”. But I think the question #3 is still not completely resolved, and still worth pursuing (though not at the hectic internet speed of the last few days).
   

8. Erik:
   donderdag 12 augustus 2010 om 19:27

   Dat wil dan zeggen dat het bewijs niet klopt? Of dat wat het artikel te vertellen had gewoon geen bewijs is van P!=NP?

Plaats een reactie