- Attempt At P ≠ NP Proof Gets Torn Apart Online
What happens when Twitter and online communities filter scientific discovery ahead of professionals? As we saw this week, a lot of fuss over a result that will ultimately be discarded into the dustbin of flawed mathematical proofs.Computer scientists have long believed that a large number of useful computational problems require an impossible amount of CPU time to solve. Decades ago it was discovered that a large set of these problems, referred to as “NP”, have so much in common that a fast solution to just one would imply a fast solution to all. But after years of no one discovering such a solution, the standard assumption for mathematicians is that no solution will be found.
But assumptions aren’t good enough for mathematicians, who prefer proofs, and have long been looking for a proof that settles that NP problems will never yield to a fast solution. In mathematical terminology, the proof they’re seeking is “P ≠ NP” (that NP problems are not equivalent to “P” problems, the kind that can be solved relatively quickly). They’ve been seeking this so long that the Clay Mathematics Institute has offered a $1,000, 000 prize to anyone who provides a valid solution.
This past Sunday HP researcher Vinay Deolalikar became the second person at HP to fall victim to the Internet fameball machine, as he posted his attempt to prove P ≠ NP on his personal website, and sent out an announcement email, which got picked up by the original formulator of the problem, Stephen Cook. Cook forwarded Deolalikar’s email to select mathematician colleagues with the now infamous statement “This appears to be a relatively serious claim to have solved P vs NP.”
Cooks’ validation email got the paper picked up by research blogs, then HackerNews, then mainstream media. Both armchair and professional math pundits proceeded to tear it apart in comments sections and subsequent blog posts, finding major flaws. Before the age of Twitter, Facebook and social news aggregation , draft research papers on something as complex as P ≠ NP would have gone through a rigorous academic process, which would focus on whether the proof strategy is correct, and whether the apparent errors are easily corrected.
Deolalikar’s proof draft was public for a day before being pounced on by the online chattering classes. When I emailed him for comment I received the following auto-response, “My email is currently backlogged; please bear with some delays in responding.” No kidding. Despite the “Please note that the final version of the paper is under preparation and will be submitted to journal review” disclaimer, heated discussion into the finer intricacies of the proof’s failures are ongoing.
Why we should care? The real world implications of P not equaling NP are that certain algorithms will take longer and certain functions in cryptography (which relies on problem solutions being difficult) will be more secure. If P were equal to NP, it would transform mathematics and the way we see the world, as many computational problems previously thought difficult could be solved, see: Traveling Salesman, Graph Coloring, etc. Most large computer systems need to solve NP problems, and currently make due with less than ideal solutions.
Or maybe because we’re all a bunch of closet wannabe math nerds?
Information provided by CrunchBase
Digest powered by RSS Digest