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."

Comments

Incompleteness

[im_thatoneguy]

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.

Re:Incompleteness

[digitig]

Fails at step 3.

Current Status

[pdxp]

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)

Re:Current Status

[Affenkopf]

The paper was preliminary to begin with. It is currently withdrawn in order to fix minor typos

Minor typos like a ! that m,ade it into the paper by accident.

Mathematicians are gathering to vet this paper

[Xenographic]

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.

Re:Mathematicians are gathering to vet this paper

[silentcoder]

>No, it's not. The relationship between computer science and mathematics is similar to the relationship between physics and mathematics:

No it's not the one IS the other and it's the perceived DIFFERENCE that doesn't exist. It's purely a perception -and a DELIBERATE illusion at that, designed to simplify the process. Ultimately it's easilly provable that every computer program is a simple mathematical function - so simple in fact that it is in fact a single number.

There is nothing weird about this- if you know lambda calculus, godel-number and Turing machines it's simple logic. We have never done anything to "split" the fields. All computer science did was to create a (very shallow) layer of pretense through which ot access the maths.

To suggest it is anything OTHER than mathematics is to prove you have absolutely no idea how computers actually work. In the real world- every computer is a universal turing machine.
If you have any real doubt - just consider this: any program COULD be written in lisp.
Lisp is DIRECTLY based on lambda-calculus - in fact the ONLY (minor) difference as small syntactical changes designed to make it easier to TYPE lambda on a computer (it was after-all designed for writing in).
Lamba-calculus is a simple form of mathematical language - like algebra or godel numbers or any of a dozen other ways to write down 2+2=4 that are all just different ways of expressing it designed to be useful for different purposes.

It's true that currently the most popular languages do not follow the lisp "look like the function you are" structure -but this is because in single-CPU machines top-down programs were slightly more similar to how the hardware actually PROCESSED the functions - and that made it easier to program in.
Expect this to change in the next few years - multi-CPU machines are actually EASIER to program for in a functional language like lisp - which makes all those nasty multithreading issues just go away by putting you on the actual mathematics that happens.

Yes, they've tried that

[Xenographic]

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.

Re:Yes, they've tried that

[nomoreunusednickname]

I have discovered a truly marvelous proof that P!=NP. But this comment is too deterministic to contain it.

I for one

[Chuck Chunder]

feel very very stupid after reading that.

Publication Bias

[mSparks43]

Like I said last time. The trouble is, every time someone proves P=NP, the NSA arranges them a little accident.

Re:Publication Bias

[martin-boundary]

You can't be sure of that. The NSA can only "accident" all those who prove P=NP if the proof verification algorithm requires polynomial time to complete.

Hard core

[gregrah]

"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.

Re:Hard core

[tehcyder]

"Formal Language Theory" - an undergrad course at my university that dealt with Finite State Automata, Touring Machines, Computability Theory, Complexity Theory,

How cool was that, I assume it was to give you a theoretical basis for the use of car analogies.

Re:Proof that a proof can't exist?

[FrangoAssado]

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?.

Re:How?

[digitig]

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.

Re:Algorithms

[Anonymous Coward]

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]?".

Dick Lipton

[Sara Chan]

For those who are unfamiliar with the name, Richard Lipton is one of the top researchers in theoretical computer science.

What would be better?

[2obvious4u]

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?

Re:It looks like

[PeterM from Berkeley]

I read that he intended his proof only to be distributed to a select group of people to help him review it. Then it got away, bits being infinitely copiable.

If someone else released his proof into the wild, we can hardly blame him.

--PM

Re:Proof that a proof can't exist?

[UnknowingFool]

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.