Tuesday, April 01, 2008

Erik Demaine proves P=NP!



  1. Would "... proves P \ne NP" be less, equally or more firstaprelish?

  2. If you proved P != NP, there would be no reason for the NSA to kidnap you, so ... less, I'd say.

  3. This is a computer-science tradition, I believe. When I was an undergrad at Rice in the 80s I saw an abstract posted for a talk by a professor Löof Lirpa showing P = NP, and mentioning, among other consequences, that henceforth all programmers would be out of work.

    In (vaguely) related news, there is an email posted on Erik's office door from a businessman who is convinced he is NP-complete (because he is very good at Minesweeper), and wants to know how to use this skill to his advantage -- "What should I do if I am NP-complete?" Not an April fool.