Slashdot Mirror
How the Web Rallied To Review the P != NP Claim
An anonymous reader writes "Remember, about a month ago, when a researcher claimed he had a proof that P != NP? Well, the proof hasn't held up. But blogs and news sites helped spur a massive, open, collaborative effort on the Internet to understand the paper and to see if its ideas could be extended. This article explains what happened, how the proof was supposed to work, and why it failed."
This quote pretty much sums it up: “Even at a conference you don’t get this kind of interaction happening,” says Suresh Venkatasubramanian of the University of Utah. “It was like the Nerd Superbowl.”
No matter the flaws with his paper, this guy has certainly managed to inspire a whole lot of people to delve into a subject and collaborate on it.
Those who think deep thoughts are precious. Those who manage to inspire thousands of others to do so...
People replying to my sig annoy me. That's why I change it all the time.
I guess I will never profit from my proof I posted a while ago since his didn't hold up:
Step #1: Wait for him to prove and confirm P!=NP
Step #2: Solve for N:
So P!=NP,
therefore P!/P=N,
thus the Ps cancel and we are left with N=!.
Step #3: ???
Step #4: Profit!
Tired of my customary (Score:1)
there should be a simpler way to go about showing that P != NP
that simpler way would only exist if P = NP
People replying to my sig annoy me. That's why I change it all the time.
Time to change again.
It is unwise to ascribe motive
We would be reading this instead:
"Remember, about a month ago, when a researcher claimed he had a proof that P != NP? Well, after a month of vigorous examination by ordinary netizens and Nobel-prize-winning mathematicians, it looks like it's going to hold up. Blogs and news sites helped spur a massive, open, collaborative effort on the Internet to understand the paper and to see if its ideas could be extended. This article explains what happened, how the proof works, and the holes experts and laymen attempted to punch in it and why the proof is still standing."
Knowledge is how to play a game, intelligence is how to win, wisdom is knowing what game to play.
This has been one of the best slashdot posts in a long, long while.
I'm gonna have to renew my subscription to Science News. Kudos to Ms. Rehmeyer.
Fuck systemd. Fuck Redhat. Fuck Soylent, too. Wait, scratch the last one.
Science may lead to facts, but it's not an automated process. Believe it or not, human emotions and intuition are involved with every scientific discovery!
There's no -1 for "I don't get it."
While the parent has been modified "funny" it really should be modified as informative or insightful. Scott Aaronson for example has discussed this issue in detail. If P=NP then we expect proofs in general in some sense to be easy but if P !=NP then in some sense proofs are difficult. (More rigorously speaking, given a well-behaved axiomatic system A, questions of the form "Is there a proof of statement s from axioms in A with the proof length at most k?" are NP-hard and for reasonable enough systems in fact NP-complete. So if P=NP proving that in some rough sense should be easy. But if P != NP then we expect proofs to be difficult. This is one of the reasons many experts actually believe P !=NP.
In fact Fermat would have himself needed a much simpler (and thus different) proof.......unless he made a mistake/made it up
www.RacquetUp.org - Helping Detroit Youth
To summarize what difficulty the proof ran into: There's a general class of NP-complete problems known as SAT. SAT is essentially given a collection of Boolean variables (so can have values "yes" or "no") and given some logical statement of those variables is there an assignment to those variables that makes the statement true? So for example, for A ^ ~ A, there isn't one, but for say A v B there are satisfactory solutions. This problem is the canonical NP-complete problem. Now, the attempted proof examined k-SAT, which is a subset of SAT known to also be NP-complete. k-SAT is the same thing as SAT but each statement must be a sequence of ands containing k inputs into set of ors. So for example if one was looking at 3-SAT "(A v B v ~ C) ^ (A v A v ~D)" would be a valid example. Now, it happens that for k>2, k-SAT is NP-complete. Deolalikar tried to examine the statistical properties of k-SAT and derive a contradiction from the assumption that k-SAT was polynomial time solvable. However, this runs into issues because from a statistical perspective 2-SAT is known to look statistically more or less the same as k-SAT, and 2-SAT is polynomial time solvable. This is a deep barrier which the proof did not overcome.
There are other deep barriers that the paper did not obviously overcome, including what is known as the "natural proof" barrier and the "relativization" barrier. The last essentially says that P=NP is true in some other computing models very similar to the standard Turing model (you consider Turing machines with special black boxes called oracles attached which answer specific questions quickly.) Similarly, it turns out that P != NP for some oracles as well. Thus, any valid resolution of P=NP will have to break down in some more or less obvious way when one tries to run the proof through for an oracle machine. If one can't point to where in a proof this would occur, this is a good indication that the proof is not valid.
Overall, I'm highly pessimistic that we are going to resolve P=NP anytime soon although I strongly believe that P != NP. There are currently much weaker claims than P=NP that we still cannot prove. We can't as far as I'm aware even get a strongly non-trivial result of the form for some explicit constant C, "No NP complete problem can be solved in polynomial time with a polynomial of degree at most C." And that's much weaker than showing that P != NP, because P !=NP is essentially that statement made for any value of C. We seem to need serious new insights and possibly lots of new machinery and structures before we can have a really good chance at cracking this nut.
I don't think you can really estimate the size of a proof by the complexity of the problem stated.
You are correct that you cannot. In fact, this is a consequence of Godel's theorem. Proof sketch: Assume we have some nice axiomatic system A, that can model the arithmetic of the natural numbers (say Peano arithmetic), and assume that this system is not stupid (axioms are recursively enumerable, valid proofs are recursively enumerable, system is consistent. I think that's all I need but there may be some other silly issues). Assume that there is a computable function f, such that any true statement in A of length n has a proof of length at most f(n). Then I claim that we can use this to resolve whether any given statement has a proof in A by looking at all proofs of length up to f(n). This contradicts standard corollaries of Godel's theorem. So no such f can exist. Thus, minimum proof length for some statements must be much longer than the length of the statements.
P!=NP
(P-1)! * P=NP
N=(P-1)!
But... the future refused to change.
This summary had three hyperlinks:
1. "claimed he had a proof"
2. "hasn't held up"
3. "spur a massive effort"
It was missing the only IMPORTANT hyperlink:
4. "this article". --- The slashdot submission was about an article. I'd like to read the article. I'd like a hyperlink which unambiguously takes me to the article. As it was, I didn't know which of the hyperlinks would take me to the article.
1. "claimed he had a proof" -- did this hyperlink take me to his claim? No: it took me to a online collaborative discussion of his claim (i.e. the original slashdot article).
2. "didn't hold up" -- did this hyperlink take me to the announcement that it didn't hold up? No: it took me to a slashdot article that maybe had a link to the statement about how it didn't hold up.
3. "spur a massive effort" -- did this hyperlink take me to that effort? Or did it take me to the spur in question? No: it took me to a REVIEW of that effort.
The hyperlinks in Slashdot summaries are always confusing.
This is definitely the kind of thing complexity theorists say. The argument fails entirely because it relies on our intuition of what easy means, and easy is not the same as polynomial, so transferring the intuition is almost intentionally misleading (not that I'm blaming you). It is basing a serious argument on an non-serious characterization of polynomial=easy that it used to help out-siders who don't know what polynomial means to never the less appreciate somewhat what complexity theory is about.
I think it's the opposite.
It's basing a non-serious argument on a serious characterization of the mathematical notion of complexity.
It's the original question, "why isn't there a simple proof of P != NP?" that is based on the layman's notion of "easy".
That the answer replaces the vague notion of "easy", with the accurately defined term "polynomial", and replaces the specific "is there an easy answer for this proof?" with the more general "proofs are NP-complete, and so we can expect it to be more complex than polynomial, assuming the thing we're trying prove is true", is not a failing of the answerer.
It's also not the failing of the questioner for being a layman. The point is, sometimes the correct answer to a question can't be put in the terms you want it to be and must, in essence, answer a different question. There are only two correct answers to the original query: "The proof of P!=NP is in the class of NP-complete problems", and "We won't know until we find it (or find the proof that P=NP)".
I personally feel one of the two conveys more useful information.
If someone asked you "How long will it take me to solve a specific but unknown instance of the Traveling Salesman problem?", you could either say: "The Traveling Salesman problem is in general NP-complete, so probably a long time", or you could say "Give me the problem and I'll let you know when I've solved it."
Since the search to find the actual solution, and thus as a side effect figure out how complex it is, is currently underway and in fact the topic of this discussion, that in the interim leaves only one useful answer.
The enemies of Democracy are