P != NP: Has it been finally proven?

[X-Act]

http://www.scribd.com/doc/35539144/pnp12pt

The paper has only been uploaded yesterday, supposedly proving that P != NP, and it hasn't been peer reviewed yet, it seems. Computer scientists and mathematicians have long suspected that P != NP, but have never proved it. For the uninformed, read this.

If you're into computer science, you should be interested in whether or not an error is found in this paper before it's published or not. :)

 

[cim]

This could possibly be one of the most important proofs in a LONG time. I look forward to reading it.

 

[chaos]

For what it's worth, tons and tons of papers have been written about P and NP... I don't think it's worth claiming that this is the real deal *yet*.

I'm gonna read it though, it looks interesting.

edit: I'm glad someone else feels the same about this. Scott Aaronson, professor of CS at MIT, bets $200,000 that this isn't the real deal. http://scottaaronson.com/blog/?p=456

scribd is awful http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_preliminary.pdf

 

[cantab]

I swear, scribd is so obnoxious when you try to download the document. Behaving exactly like so many of the spamming crapps on Facebook. :-@

If correct, this result is, of course, huge. EDIT: That said, would it advance mathematics or computing that much. P != NP is believed to be the case anyway. Can anything important be built on that? I expect proving two things are not the same is in general a lot less useful than proving two things are the same.

If wrong...it could have a big negative impact on mathematicians' confidence in general, as well as provoke criticism of the practice of online publication of non-peer-reviewed work.

I'm no mathematician, but it does strike me as odd that approaches derived from stastics are being used in the proof of an "absolute" theorem.

 

[vonFiedler]

It takes this much paperwork to prove a theory and my mother always wonders why I'm not a mathematician.

I suppose it'd behoove me to read all 103 pages, but I've read these before without results and I honestly never had a strong opinion on the matter. The theory stems from the fact that the opposition has no proof, which is not proof. If this paper is the real deal, I'm sure I'll hear about it soon enough.

 

[chaos]

It takes this much paperwork to prove a theory and my mother always wonders why I'm not a mathematician.

I suppose it'd behoove me to read all 103 pages, but I've read these before without results and I honestly never had a strong opinion on the matter. The theory stems from the fact that the opposition has no proof, which is not proof. If this paper is the real deal, I'm sure I'll hear about it soon enough.

Well, most papers are 8-15 pages... this is a pretty big result to prove. Anyway, the only part that proves anything is the last section. The rest is review of the various fields he draws inspiration from.

Also, you mean theorem, not theory :)

 

[vonFiedler]

Well, most papers are 8-15 pages... this is a pretty big result to prove. Anyway, the only part that proves anything is the last section. The rest is review of the various fields he draws inspiration from.

Also, you mean theorem, not theory :)

Yeah, that thing. I could read the last part, but if he felt it was important to write all the stuff where he drew inspiration from then it's probably worth reading. I'd rather completely blow something off than half ass it.

 

[drifblim70]

this is one of those big unsolved mathematical question things, right? think I saw it on wikipedia at some point and barely understood it, can someone explain what P!=NP means (or would mean) and what it would mean if it was proven (like the consequences of it)?
I just finished first year calculus and haven't done much computer science, so ah, if it's too complicated, whatever...

 

[cantab]

Very roughly speaking:

'P' problems are easy to solve (in terms of computing power needed).
'NP' problems are easy to check the answer, but not necessarily easy to solve.

The question is whether all NP problems are in fact P. Were that the case a lot of important problems would have easy solutions. It's long been suspected that NOT all NP problems are P. This paper, if it is correct, proves that suspicion.

 

[skarm]

For the uninformed, read this.

I read it and I still have no absolute clue what it is talking about beyond simple layman terms. However, I do follow some of Millennium Prize Problem(s) stuff so I do find this exciting, although not likely on any level that Computer Science and Math majors do.

 

[Morm]

Yeah, from what I got from X-acts link there it seems that if a computer can check if a solution is right it can create the solution itself. I therefore speculate, based on that one sentence of experience in the field of computer science, that it's an important step towards AI. Am I right or way out to lunch?

 

[chaos]

I'm not sure what you mean by important step towards AI... but if this paper is correct, "nothing changes" because most people think P != NP anyway.

 

[Pidge]

I read it and I still have no absolute clue what it is talking about beyond simple layman terms. However, I do follow some of Millennium Prize Problem(s) stuff so I do find this exciting, although not likely on any level that Computer Science and Math majors do.

I found this link to be easier to understand, although probably not as informative:

http://www.claymath.org/millennium/P_vs_NP/

 

[vonFiedler]

I'm not sure what you mean by important step towards AI...

He means in terms of AI that solve problems by themselves, and that's not what P=!NP is about. However for an NP problem, we don't build an AI to figure out the problem. We figure out the problem, we just need the computer to do extra legwork for us. So it's really got nothing to do with AI.

 

[MrIndigo]

It'll be a while before this can be verified.

There was a paper posted up on ArXiV not long ago claiming to have used geometric methods to prove the Reimann Hypothesis. It turned out to be quite shallow and flawed.

 

[cantab]

Thinking about it, the cynic in me wonders if this is to some extent a publicity stunt organised by scribd.

 

[Morm]

ohhh I see a little more. See, that's what I get for speculating after such limited experience!

 

[skarm]

Thinking about it, the cynic in me wonders if this is to some extent a publicity stunt organised by scribd.

That would be a poor idea. While it is clearly generating publicity right now, but too many of these with false claims or "big discoveries" ridden with wholes would only serve to ruin their reputation in the academic world in the long run.

 

[cantab]

To clarify: it benefits scribd, not the academics. I'd bet it's the single most viewed document on there right now.

 

[chaos]

It's not organized by scribd. This guy is a legitimate researcher and his PDF was leaked by a blogger without his permission. In my first post in this thread I link to a PDF on his website. I don't know why anyone would think scribd has anything to do with this.

 

[cantab]

OK, I stand corrected, I overlooked that link originally.

As for why I'd think that - I'm jaded, cynical, and distrustful.

 

[chaos]

I've been following Scott Aaronson and Richard Lipton's blogs on this:

Anyway, it seems that the “proof” is toast. As I mentioned before, the big (meta-)problem of this paper is hand-waving: when you get to the details you see that the arguments are not spell out in a precise enough manner. This led to a comment I’ve just seen on Lipton’s blog, made by Charanjit Jutla (of IBM T.J. Watson). He talks about an easy to spot (unfixable) problem in the proof, caused by a non careful use of fixed point logic.

Serious (unfixable) problem.
Vinay uses FO(LFP) as his main tool. However, I think he fails to realize that FO(LFP) , although defined using least fixed point, also contains greates fixed points.
Thus, if \mu x f(y,x) is the formula denoting least fixpont of f(y,x) under x,
and \nu x f(y,x) is the formula denoting greates fixpont of f(y,x0 undex x,
then there is this triple negation rule:
\neg \mu x \neg f(y, \neg x) = \nu x f(y,x). (See Kozen’s paper on axiomatizing Mu-Calculus, or my paper with Allen Emerson on Mu-Calculus in FOCS 1991 titled “Mu-Calcus, Tree Automata and Determinacy”, or just original Vardi and Immerman papers). Note that the left hand side is well defined in LFP, as x is under even number of negations from the operator \mu.
Now, his whole theory of least fixed point only increasing the size of the structures falls apart. BTW, this is a usual mistake most people new to fixed-point logics fall prey to.
For example, now he has to deal with formulas of the kind
\nu x (f(y, x) \and g(y, x)).
His section 4.2 deals with just one least fixed point operator…where his idea is correct.
But, in the next section 4.3, where he deals with complex fixed point iterations, he is just
hand waving, and possibly way off. Given that he does not even mention greatest fixed points leads me to think that this is a huge (unfixable) gap.
Charanjit Jutla
IBM T.J. Watson

Of course, someone else says:

LFP on finite structures with order reduces to a single least fixpoint.
(That’s why the LFP = P proof works.) That’s why the question of what he’s doing with order, is important. I don’t understand what he’s trying to do, but people I trust assure me the paper is obvious nonsense, so I’ve only skimmed it.