Forgot your password?
typodupeerror
Math Science

How the Web Rallied To Review the P != NP Claim 160

Posted by Soulskill
from the peer-to-peer-review dept.
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 discussion has been archived. No new comments can be posted.

How the Web Rallied To Review the P != NP Claim

Comments Filter:
  • by JoshuaZ (1134087) on Friday September 10, 2010 @04:23PM (#33538444) Homepage
    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.
  • by JoshuaZ (1134087) on Friday September 10, 2010 @04:40PM (#33538674) Homepage

    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.

  • by JoshuaZ (1134087) on Friday September 10, 2010 @05:00PM (#33538878) Homepage

    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.

  • Re:The greatest gift (Score:5, Informative)

    by phaunt (1079975) * on Friday September 10, 2010 @06:27PM (#33540110)
    That's exactly what he did. He mailed it to a small group of experts and asked them for their comments. Some of them sent it on, commenting: "hey, this looks like a legit attempt", and before Vinay knew it, his article was on the web.
  • by gfody (514448) on Friday September 10, 2010 @07:17PM (#33540674)
    Try P vs NP for dummies [qntm.org]
  • by oldhack (1037484) on Friday September 10, 2010 @08:40PM (#33541340)

    She elaborates later on that, if P=NP, the proof will provide general hint in transforming NP into P whose solution can be more easily found, hence the "mind-boggling" possibilities of solving many problems currently thought infeasible to solve.

    "Assuming" P=NP doesn't help because we don't know in general how to transform NP into P or if it's even possible. In fact, it's suspected it's impossible so one will never likely even to try.

  • by Anonymous Coward on Friday September 10, 2010 @10:27PM (#33541834)

    Yeah, instead what we read is:

    "I have fixed all the issues that were raised about the preliminary version in a revised manuscript; clarified some concepts; and obtained simpler proofs of several claims. Once I hear back from the journal as part of due process, I will put up the final version on this website." - http://www.hpl.hp.com/personal/Vinay_Deolalikar/

    Oh hey, that's practically the same thing.

  • by Anonymous Coward on Saturday September 11, 2010 @02:58AM (#33542886)

    The undecidability of the halting problem is the CompSci version of Godel's Theorem: they are in fact logically equivalent, and each can be proved from the other.

You can do this in a number of ways. IBM chose to do all of them. Why do you find that funny? -- D. Taylor, Computer Science 350

Working...