A Proof that P != NP from Vinay Deolalikar of HP Labs

Slashdot[1] brought this up first (at least to the Internet at large) and then came postings on Schneiers' blog [2] which also references [3]. There was also a small post in comp.compression that referenced [4].

It appears to be a serious effort but of course it is still very early to know for sure what is going on. There's a group of folks [5] (including Terence Tao) who are looking into the paper (or whatever has been published). And of course Slashdot has an update[6].

As for the basic stuff it is here[7] and here[8].

Interesting times lie ahead...

URL[1]: http://science.slashdot.org/story/10/08/08/226227/Claimed-Proof-That-P--NP
URL[2]: http://www.schneier.com/blog/archives/2010/08/p_np_1.html
URL[3]: http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/
URL[4]: http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%e2%89%a0np/
URL[5]: http://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p%e2%89%a0np/
URL[6]: http://science.slashdot.org/story/10/08/11/0239209/Possible-Issues-With-the-P--NP-Proof
URL[7]: http://en.wikipedia.org/wiki/P_versus_NP_problem
URL[8]: http://www.claymath.org/millennium/P_vs_NP/

[/readings] permanent link

Quote of the Day for 2010-08-09

We who lived in concentration camps can remember the men who walked through
the huts comforting others, giving away their last piece of bread. They may
have been few in number, but they offer sufficient proof that everything
can be taken from a man but one thing: the last of the human freedoms -- to
choose one's attitude in any given set of circumstances, to choose one's
own way. 
        -- Viktor Frankl, author, neurologist and psychiatrist, Holocaust
           survivor (1905-1997)

[/quotes] permanent link

EFF SSL Observatory

The EFF[1] has an interesting project going on - an SSL Observatory [2]. They've collected a fairly large set of SSL certificates from various (public) IPs that are running an SSL enabled HTTPS server on port 443 and then done some analysis on the various aspects of the certificates. It is a very nice study and points out how many "poorly" implemented SSL servers there are out there. They also mention some bits (pun intended) about the Debian SSL [3,4] issue as well. The accompanying presentations (PDFs, [5] and [6] are very nice reads as well. Thanks to LWN [7] for pointing this out.

URL[1]: https://www.eff.org/
URL[2]: https://www.eff.org/observatory
URL[3]: http://digitaloffense.net/tools/debian-openssl/
URL[4]: http://wiki.debian.org/SSLkeys
URL[5]: https://www.eff.org/files/DefconSSLiverse.pdf
URL[6]: https://www.eff.org/files/map-of-CAs.pdf
URL[7]: http://lwn.net/Articles/398857/

[/technology] permanent link