Slashdot Mirror
Possible Issues With the P != NP Proof
An anonymous reader writes "We previously discussed news that Vinay Deolalikar, a Principal Research Scientist at HP Labs, wrote a paper that claimed to prove P is not equal to NP. Dick Lipton, a Professor of Computer Science at Georgia Tech, analyzed the idea of the proof on his blog. In a recent post, he explains that there have been many serious objections raised about the proof. The post summarizes the issues that need to be answered in any subsequent development, and additional concerns are raised in the comment section."
I haven't been this confused since reading Godel's Proof.
Yes there can be a proof to prove that there is no proof. Check out Godel's Incompleteness Theorem
http://en.wikipedia.org/wiki/G%C3%B6del's_incompleteness_theorems
Gödel's incompleteness theorems are two theorems of mathematical logic that establish inherent limitations of all but the most trivial axiomatic systems for mathematics. The theorems, proven by Kurt Gödel in 1931, are important both in mathematical logic and in the philosophy of mathematics. The two results are widely interpreted as showing that Hilbert's program to find a complete and consistent set of axioms for all of mathematics is impossible, thus giving a negative answer to Hilbert's second problem.
Not sure if any such effort exists though in this case.
The paper was preliminary to begin with. It is currently withdrawn in order to fix minor typos and because currently "enough unresolved issues with the paper exist to foster a healthy sense of skepticism". This is a good thing for now.
The original discussion was in a Google Doc but has since moved to a wiki.
Info: Previous post explaining the proof more clearly
Paper (not wort reading for most of us)
You're not alone. Normally, my undergraduate math courses and Wikipedia are enough for me to at least explain the concept to laymen. I'm at a loss in this case.
For anyone interested in the details, you can find a lot more on this wiki, where a lot of mathematicians are weighing in on the proof and its potential flaws. Mathematicians are gathering from all over to examine this paper because it's so interesting. Even if one of the serious objections that have been raised so far kills it, it contains some novel ideas that will get people thinking.
They've also been gathering the news coverage and such, so it's probably the best place to find up-to-date information about this proof. It seems to have sparked quite a lot of interest for a paper that hasn't even been properly published.
buffer overflow exploits, quantum physics, the pre-big bang universe and phone company math make my head hurt. Understanding this sort of thing must be like having a set of truck nuts hanging from your geek card.
---
DRM is like antifreeze, to the MPAA/RIAA it's sweet, to the consumers it's poison.
They've tried that, but all that's been proven so far is that several types of proof won't work, rather than proving that it's impossible to prove. The first few sections of this paper itself go into detail about why this proof isn't one of the kinds of proof that won't work, incidentally.
Terrence Tao has a blog post on why a P=NP proof can't be relativisable if you're interested. Incidentally, there are several other classes of proof that won't separate P from NP.
(I am not a mathematician)
If a proof that P=NP is undecidable exists then P=NP is decidable.
If P=NP then there is a polynomial time reduction from a P problem to an NP complete problem. That algorithm is sufficient to prove that P=NP.
If P=NP is undecidable then no such algorithm can exist and therefore P!=NP.
Therefore a proof that P=NP is undecidable is sufficient to prove that P!=NP and therefore P!=NP cannot be proven to be undecidable.
(The only loophole I can see is that the algorithm could exist but could not be proven to run in polynomial time)
Tim.
God said, "div D = rho, div B = 0, curl E = -@B/@t, curl H = J + @D/@t," and there was light.
feel very very stupid after reading that.
Boffoonery - downloadable Comedy Benefit for Bletchley Park
Like I said last time. The trouble is, every time someone proves P=NP, the NSA arranges them a little accident.
"Formal Language Theory" - an undergrad course at my university that dealt with Finite State Automata, Touring Machines, Computability Theory, Complexity Theory, and the formal proofs thereof, was the most interesting class that I've ever taken. That being said, I always felt when doing homework for that class that I was taking a dive off the deep end (i.e. pushing the limits of human sanity). And that's only from studying the "low hanging fruit" that people were publishing papers on several decades ago when theoretical computer science was still relatively young. I can't imagine things have gotten any less mind-warpingly complex since then.
I have tremendous respect for the folks who continue to "dabble" in this stuff. I'm sure that for their efforts they have been rewarded with glimpses of indescribably beautiful works of both man and of nature.
Vinay Deolalikar was a little unfortunate in that his unreviewed theory got more attention than he believed it would. It seems his paper offers a new approach, but as it was a first draft had a number of holes and was by no means ready for "prime time".
On the other hand, you could say that broadcasting that you have a solution to one of the most famous remaining unsolved problems was a little ill-advised.
Donte Alistair Anderson Roberts - hi son!
Karma: Chameleon
This question has been considered by quite a few different people; search google for P vs NP independent ("independent" meaning independent from the usual accepted axioms for mathematics, i.e., can't be proven using the currently accepted axioms).
There's a nice survey paper about this question that's very readable if you're willing to invest some time: Is P Versus NP Formally Independent?.
Step 3 states that "We cannot accept the definition of the set NP purely in terms of its members having a property (a solution in polynomial time) that we have no reliable mechanism to detect." "Detect" is a bit vague here, but all that's needed for an existence proof (or disproof) is a formal definition, not any means of actually detecting cases. Look at pretty much any proof involving transfinites.
Quidnam Latine loqui modo coepi?
Furthermore, this guy is asking for a "complete and consistant" definition.
In the Incompleteness Theorem, a system of axioms is complete if, for all statements in the system, either the statement or its negation is provable from the axioms. A system is consistant if there exist no statements for which both the statement and its negation are provable.
Basically, his "proof" is "Hey, we don't want a contradictory or unfinished definition, right? And those words mean the same thing as consistant and complete! So, Godel!"
How about this simplification:
P is the class of problems for which you can get the answer (output) quickly (i.e. in polytime).
NP is the class of problems for which you can verify an answer quickly.
P = NP is the question of whether all problems where you can verify the answer quickly have corresponding solvers that also find the answer quickly. If yes, P = NP, if not, P != NP. It's really a question about how powerful algorithms can be - and thus how powerful intelligence can be, because if P = NP, you could build a puzzle solver that would solve just about any puzzle, including "is there a short proof for [insert conjecture here]?".
Thank you.
Also, thinking of that just blew my mind. Now I hope that P == NP would really be true because of all the possibilities...
Couple of things: Irrespective of whether P = NP or not, there exists polynomial-time reductions from any problem in P to any NP-complete problem. I guess you meant it the other way round.
I am not sure in what sense you use the term "undecidable", but if (as it seems likely) you used it to mean independent , then your argument fails at steps 2 and 3.
A proof that P =? NP is undecidable has to only show that one can neither prove nor disprove this statement: it need not show that no polynomial-time reduction exists from from any NP-complete problem to any problem in P.
In other words, undecidable != false.
Then could you be more precise about what you mean by "undetectable", what the problem is with "undetectable" theorems, and in what sense is P a theorem?
Quidnam Latine loqui modo coepi?
I don't buy that nearly as many people on here understood that as are going to post on here acting like they understood that.
Hopefully one of Slashdot's crack editors will repost a lighter story this morning to comment on ...
For those who are unfamiliar with the name, Richard Lipton is one of the top researchers in theoretical computer science.
If you think 'polynomial time' and 'quickly' are in any way similar, there's a good chance that you're a theoretical computer scientist.
I am TheRaven on Soylent News
Finding a proof for P=NP or P!=NP?
In one case encryption can be proven secure, in the other we loose encryption but gain efficiency. What would be better for humanity going forward, being able to solve box packing problems instantly or having nearly perfectly secure communication?
Can the proof be verified in polynomial time?
I'm one of those ex-mathamaticians who still sulks at the existence of discussions beyond my ability to comprehend, where there is absolutely nothing constructive I can add. As a student back in the day, I was always nervous of proofs that were longer than a page - it always seemed to me that once a single proof got beyond a certain length, there was always some lingering doubt that some flaw or special condition had been overlooked, doubt that would pass on to every result that then used it. I guess that's the difference between learning math (where the problems are deliberately selected by textbook authors to have nicely bounded complexity) and researching math (where nobody knows how many twists and turns there are in the road between you and your goal).
The paper may target the wrong hardness phase of randomized {k}-SAT.
Not really. It's proof of a negative which is vastly more difficult than a positive. For example, proving no dogs can have black spots is much harder than dogs can have black spots. You'd have to prove how it's impossible for any dog in existence to get black spots. The opposite only requires existence of 1 dog with black spots.
It's the same with Fermat's Last Theorem: Prove no solutions exist for x^n+y^n=z^n for all integers x,y,z where n is an integer greater than 2. That proof takes hundreds of pages.
Well, there's spam egg sausage and spam, that's not got much spam in it.
I am a layman (not a mathematician) however there are several large points of suspicion that I can identify with this proof. First of all, its 102 pages long. Second of all, its a proof by contradiction, namely that certain known statistical behaviors of a formula are contradicted for the author's constructions if P=NP. So in reality, a proof like this requires not only examination of the particular proof in question, but of all other theorems and inferences that are relied upon to construct the contradiction as well. Given the already enormous length of the proof (102 pages), in addition to all related theorems and inferences (thousands of pages?) that must _also_ be correct, it will take a long time to 'verify'.
This is a good reason for computer checked proofs:
http://www.zdnet.com/blog/emergingtech/computers-checking-mathematical-proofs/1087
--"You are your own God"--
Irregardless is not a valid word.
Note this is from a respected MIT prof:
My hunch is he's pretty sure it's broken.
I stole this Sig
Strictly speaking, every computer in the real world is a finite state machine that's complex enough to simulate a universal Turing machine.
Not exactly. A finite state machine cannot represent the unbounded tape of a universal Turing machine. I prefer to model computers as deterministic linear bounded automata, which are identical to Turing machines except that they cannot advance the index past the end of the input. Each LBA has an equivalent FSM, but unlike an FSM, an LBA has an index, which allows reasoning about arrays and pointers.
the mathematical operations that comprise a function is the function it is, and nothing looks more like that than the underlying assembly.
Assembly language doesn't have a notion of types. For example, the Python expression [x + 5 for x in some_list] starts with a list (or other iterable item) and ends with a list. Assembly language has to explicitly loop over the elements, apply the operation, write back the result, and hope the rest of the program treats it as a list.
You can call it math if you want, but if I can write a program to do what I want to do, it makes no difference to me if it's math or not.
The difference is that a computer can be perfectly modeled by math because all operations on a computer are mathematical. Your example of moving a rock include incompletely modeled physical fields such as robotics (how to move the limb that moves the rocks) and computer vision (how to determine where to place the rocks so that they don't fall).