WebliminalBlog

Links about P vs NP

• Has the Devilish Math Problem “P vs NP” Finally Been Solved? | 80beats | Discover Magazine – “P is not equal to NP. Seems simple enough. But if it’s true, it could be the answer to a problem computer scientists have wrestled for decades.
  Vinay Deolalikar, who is with Hewlett-Packard Labs, has sent to peers copies of a proof he did stating that P is not equal to NP. “
• The Status of the P Versus NP Problem | September 2009 | Communications of the ACM – “The theory of NP-completeness helps us understand these limitations and the P versus NP problem begins to loom large not just as an interesting theoretical question in computer science, but as a basic principle that permeates all the sciences.”
• A compendium of NP optimization problems – “This is a continuously updated catalog of approximability results for NP optimization problems. The compendium is also a part of the book Complexity and Approximation. The compendium has not been updated for a while, so there might exist recent results that are not mentioned in the compendium. If you happen to notice such a missing result, please report it to us using the web forms.”
• CMU professor honored for computational complexity breakthrough – ” In a paper presented at the Symposium on Theory of Computing in 1994 and published in 1997 in the Journal of Computer and System Sciences, they showed that a wide class of proof techniques they call “natural proofs” can’t solve the P vs. NP question. What’s more, they found that those previous results turned out to have an almost contradictory double life, providing methods for breaking a wide class of cryptosystems.”