typodupeerror

Possible Issues With the P != NP Proof147

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."
This discussion has been archived. No new comments can be posted.

Possible Issues With the P != NP Proof

• What? (Score:1, Interesting)

I haven't been this confused since reading Godel's Proof.
• Current Status (Score:5, Informative)

on Wednesday August 11, 2010 @02:42AM (#33212654)
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 [michaelnielsen.org].

Info: Previous post explaining the proof more clearly [wordpress.com]
Paper [hp.com] (not wort reading for most of us)
• Re:Current Status (Score:5, Funny)

on Wednesday August 11, 2010 @04:09AM (#33212900)

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 (Score:5, Informative)

on Wednesday August 11, 2010 @02:50AM (#33212680) Journal

For anyone interested in the details, you can find a lot more on this wiki [michaelnielsen.org], 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: (Score:2)

If there is a problem but someone else solves it, who gets the prize?

• Re: (Score:2)

I suppose the OP but he could choose to share a part of the money to show fair play.
• Re: (Score:1, Insightful)

by Anonymous Coward

Indeed.

Irregardless of whether he's correct or not, the fact that he came out and made it public to be vetted is quite ballsy. Further, the discussion it generates *cannot* be a negative thing.

Kudos to Vinay Deolalikar. You've brought about a minor storm that will bring about positive results.

• Free vocabulary lesson. (Score:2, Informative)

Irregardless is not a valid word.

• Publication Bias (Score:5, Funny)

on Wednesday August 11, 2010 @03:37AM (#33212806) Homepage Journal
Like I said last time. The trouble is, every time someone proves P=NP, the NSA arranges them a little accident.
• Re:Publication Bias (Score:5, Funny)

on Wednesday August 11, 2010 @05:16AM (#33213070)
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.
• Re: (Score:1, Troll)

P=NP is a question in computer science, not mathematics. The two fields split about 50 years ago.

• Re: (Score:2)

P=NP is a question in computer science, not mathematics. The two fields split about 50 years ago.

But computer science is mathematics, or rather a subset thereof.

• Re: (Score:1, Troll)

But computer science is mathematics, or rather a subset thereof.

No, it's not. The relationship between computer science and mathematics is similar to the relationship between physics and mathematics: there is some overlap, lots of fruitful cooperation, and some fundamental differences in methodology and subject matter.

Even if computer science were a subset, it's only the computer scientists that are gathering to vet this paper. Saying "mathematicians are gathering to vet this paper" would be as misleading

• Re:Mathematicians are gathering to vet this paper (Score:5, Insightful)

on Wednesday August 11, 2010 @10:48AM (#33215452)

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

• Re: (Score:1)

Computer science is not a subset of mathematics - rather, mathematics is a subset of computer science. Any question in mathematics can be restated as a question about Turing machines. The question "Can the statement x be proven theory T?" can be restated as, does Turing machine PM(x,T) halt, where PM is a rather simple Turing machine that tries out all potential proofs of x using axioms of theory T (usually there's inifinitely many proofs to try) and halts if it finds a valid proof. You could say that comp
• Re: (Score:3, Funny)

CS is a subset of biology. Any question in CS can and must be restated in a human brain...

• Re: (Score:2)

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

That may satisfy the folks who can o

• Assembly language is typeless (Score:2)

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.

• Re: (Score:1)

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.

Or, in assembly, you could implement functions which verify the type of parameters and branch to exception code if they don't match. Which is exactly what Python is doing unde

• Re: (Score:2)

everything a computer does is just math and can be translated into any equivalent math and you'll get the same result

Being able to simulate and model something at a low level doesn't give you a high level understanding. A mathematician understands boolean logic, but that doesn't mean he has the knowledge and skills to design a CPU or program it. That knowledge and those skills aren't taught in mathematics, they are taught in computer science.

• Re: (Score:2)

Being able to simulate and model something at a low level doesn't give you a high level understanding. A mathematician understands boolean logic, but that doesn't mean he has the knowledge and skills to design a CPU or program it. That knowledge and those skills aren't taught in mathematics, they are taught in computer science.

Yes, you are completely correct to say that the specific disciplines necessary to write computer programs, or to design a CPU (which is a combination of computer science and electrica

• Re: (Score:2)

Is math and is covered by mathematics degree programs are completely orthogonal properties.

Nevetheless, it is computer scientists, not mathematicians, that are gathering to to vet this paper: if you work on the theory of computation, you are a computer scientist, no matter what your training, background, or methods.

• Re: (Score:2)

>. A mathematician understands boolean logic, but that doesn't mean he has the knowledge and skills to design a CPU or program it. That knowledge and those skills aren't taught in mathematics, they are taught in computer science.

This is a half-truth at best. Firstly because the knowledge to design a CPU isn't taught in computer science either - it's taught in electronic engineering. The real problem is that so few people today actually studied computer science - learning programming != computer science.

• Re: (Score:2)

learning programming != computer science

Correct: learning to program is a strict subset of computer science. (CPU and VLSI design may or may not have branched off from computer science now, that's debatable.)

There's a REASON that most of the algorithms we use every day were originally designed by people like Donald Knuth - who are professional MATHEMATICIANS.

Donald Knuth was trained as a mathematician before computer science existed, but today he is a computer scientists at the computer science department.

• Re: (Score:2)

>Donald Knuth was trained as a mathematician before computer science existed, but today he is a computer scientists at the computer science department. Go check his home page.

You know there are OTHER specialized subfields of mathematics - and Knuth is among the primary people standing behind the belief that computer science is maths - and has testified in the supreme court his belief that it is such pure maths that it should be unpatentable.

>Be that as it may, it's computer scientists, not mathematici

• Re: (Score:2)

Speaking as a total non-mathematician here...

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.

OK fine, but if untyped lambda calculus is a form of notation that's useful for describing computation, isn't this a circular argument? It's a computer. Of course a form of notation used to express computation would be able to describe what it does.

If, on the other hand, I want to describe a system where I have a bunch of rocks in one pile, and I move rocks to another pile based on certain logical criteria, forming a kind of "loop" ... couldn't that also be expre

• Perfect mathematical model of a computer (Score:2)

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

• Re: (Score:2)

So in the end, your comments sound like the same kind of navel-gazing that says "math is everywhere" .... "Look, Bobby, see the Golden Ratio in the structure of this leaf? Math is everywhere!" "No dad, that is not math. That is a leaf. Math is how you think about the leaf."

Right. The leaf can be described by math. Math is the description, an abstract representation of the concept of how the leaf is structured.

A computer program is nothing more than an abstract representation of mathematical operations. "

• Re: (Score:2)

>OK fine, but if untyped lambda calculus is a form of notation that's useful for describing computation, isn't this a circular argument?
In a sense being circular makes it true - because you can translate between a form of pure maths, and a computer language that's a "circle" - the fact that the meaning remains utterly unchanged throughout the circle means they are identical.

>It's a computer. Of course a form of notation used to express computation would be able to describe what it does.

You think that'

• Re: (Score:3, Informative)

You don't REALLY need to CAPITALIZE words so FREQUENTLY to make your point.

• Re: (Score:2)

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.

Cool... and since most porn is digital now, and displayed on computers, can we then say that porn is just a calculation in lambda calculus?

Who knew that watching porn was the equivalent of doing calculus!!!

• Re: (Score:2)

more like watching a machine perform pre-constructed calculus. But hey, who's keeping score? Fap away.

• Re: (Score:2)

Cool... and since most porn is digital now, and displayed on computers, can we then say that porn is just a calculation in lambda calculus?

I'm sure I don't need to explain the difference between an algorithm and a dataset.

• Re: (Score:3, Insightful)

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.

Every biological system is a physical system, but if you study physics, you'll know next to nothing about biology.

All computer science did was to create a (very shallow) layer of pretense through which ot access the maths.

There is no "pretense". Theoretical computer science is a highly mathematical discipline, but it deals with issues that are of no interest

• Re: (Score:2)

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

>Every biological system is a physical system, but if you study physics, you'll know next to nothing about biology.

If you do the quantum wave functions for every particle in the cat, in the milk, in the floor... you can predict that the cat will drink the milk. It's in there - though granted with current technology it would take us longer than the e

• Re: (Score:2)

Really, can't a very similar argument be applied to nearly every field of applied knowledge? Mathematics is a model for how the universe works; all practical science is just applied mathematics in some form or another. Music, anthropology, biology, conspiracy theories--they can all be described as applications of mathematics.
• Re: (Score:2)

All those things existed before mathematics, were not created by mathematicians, and exist independently of whether mathematics did or not.
We use mathematics to describe them but they all predate it.

Computer science doesn't share ANY of those traits. It did not, indeed COULD NOT exist before mathematics, it was created BY mathematicians and it cannot exist indepently of mathematics.
That's why it is in fact wrong to claim that it's APPLIED mathematics (though it's useful to think that way) - it isn't, it IS

• Re: (Score:2)

Au contraire. I don't refer to the things those sciences are used to manipulate, but the sciences themselves. Those ways of looking at the world are fundamentally built upon mathematics.
• Re: (Score:2)

Mathematics is a model for how the universe works

Uh, no its not. Mathematics is *used* to model how the universe works, but it's not, itself, a model.

• This and... (Score:1)

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.

• Re: (Score:2)

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.

Those are all very different things that require very different skills and interests.

• Buffer overflow exploits: Needs little intelligence to understand, but a small amount of background knowledge.
Field: Computers.
Geek score: 1
• Quantum physics: Needs average intelligence, but a fair amount of backgr
• Re: (Score:2)

Most mathematicians would not understand a lot of the things in that proof, barring research, unless they were into abstract algebra and group theory. I tried to read through it a bit and holy shit it was difficult. Its mostly that Im not used to seeing things presented that way, with a fair share of WTF thrown in over topics Ive never been exposed to.
• I for one (Score:5, Funny)

on Wednesday August 11, 2010 @03:31AM (#33212786) Homepage Journal
feel very very stupid after reading that.
• Re: (Score:1, Funny)

It's not that hard, just try to stay with me...

P != NP
NP has an N in it
So it's not the same as P
P != NP
QEDuh!

If you need any help with any other math stuff, just let me know.

• Re: (Score:1)

It's not that hard; try to stay with me:

P != NP
NP has an N in it
So it's not the same as P
P != NP
QEDuh!

If you need any help with any other math stuff, just let me know.

• Re: (Score:3, Insightful)

NP has an N in it
So it's not the same as P

Prove it.

• Re: (Score:1)

Stupid and ignorant are not the same thing. Confusing them is a common geek fallacy.

• Re: (Score:2)

No no, I'm pretty sure he means stupid.

I feel the same way, but I pretend like I'm just ignorant when I read it. Makes me feel better. ;)

• Hard core (Score:5, Interesting)

on Wednesday August 11, 2010 @03:38AM (#33212810)
"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 (Score:5, Funny)

on Wednesday August 11, 2010 @04:26AM (#33212958) Journal

"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: (Score:2)

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

More likely they were thrown on a bike in the midst of the Tour de France w/o the helmet.

• Re: (Score:1)

I also took formal language theory and found it to be one of the most thought provoking classes I ever took as well as one of the most difficult. The bi weekly assignments would take me about 20 hours, but man I learned a lot, including how to program a turing machine, an exercise in abstraction which still blows my mind. I'd like to give a big shoutout to my professor, David Barrington, an amazing teacher who also seems to be doing very interesting work in the analysis of this paper. See links to his posts
• It looks like (Score:2, Insightful)

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.

• Re:It looks like (Score:4, Insightful)

<petermardahl@@@yahoo...com> on Wednesday August 11, 2010 @09:49AM (#33214776) Journal

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: (Score:2)

I think he knew exactly how much attention his paper would get.

What he probably didn't know is that were disturbing flaws within it.

Even so, he was humble enough to RFC instead of just publishing it.

• Okay honestly ... (Score:2)

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

• Dick Lipton (Score:4, Informative)

on Wednesday August 11, 2010 @08:01AM (#33213754)
For those who are unfamiliar with the name, Richard Lipton [wikipedia.org] is one of the top researchers in theoretical computer science.
• Re: (Score:2)

And he has a funny name in the proud tradition of Lipschitz.

• Re: (Score:2)

He also knows a lot about tea, and decided he makes more money by selling the shitty kind.

• Re: (Score:2)

He also knows a lot about tea, and decided he makes more money by selling the shitty kind.

Cheap/easy to use. Universal appeal.

• Re: (Score:1)

Lipton was one of the co-authors of a great analysis called "Social Processes and Proofs of Theorems and Programs" (http://www.cs.umd.edu/~gasarch/BLOGPAPERS/social.pdf). It points out how a very complex proof is only as valid as the community of scientists who believe it. There are great risks for subtle lapses of logic in a 90 page proof and at best, a distinguished team of reviewers can only agree that they have not found a flaw. That said, the P != NP proof is great in that it has started a new socia
• What would be better? (Score:4, Interesting)

on Wednesday August 11, 2010 @09:29AM (#33214552)
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: (Score:3)

We can do cryptography without relying on P!=NP. That's going to be longer to initialize but that would probably work.

• Re: (Score:3)

Intuition suggests that improvable worlds would be better than universes set in proverbial stone, so P = NP. Even if we can't prove a lemma, that kind of world doesn't rule out accidental proofs by dumb luck or alien intelligence. Personally, assuming I kinda grok the basics, there are more cases of improvable than provable, such as Sylvain Gelly's MoGo program which can beat average Go players about five decades sooner than expected. P = NP means live is easy, imho.
• Problem solving (Score:3, Interesting)

on Wednesday August 11, 2010 @09:36AM (#33214648) Journal

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

• Re: (Score:2)

From my virtually non-existent understanding of this problem, it sounds like issues surrounding polynomial time are where the bulk, if not all, of the issues raised about the proof lie.

• Well, duh... (Score:1)

The paper may target the wrong hardness phase of randomized {k}-SAT.

• A Layman's Take (Score:1)

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 contradi

• Scott Aaronson's take (Score:2)

Note this is from a respected MIT prof: [scottaaronson.com]

If Vinay Deolalikar is awarded the \$1,000,000 Clay Millennium Prize for his proof of PNP, then I, Scott Aaronson, will personally supplement his prize by the amount of \$200,000.

I’m dead serious—and I can afford it about as well as you’d think I can.

My hunch is he's pretty sure it's broken.

Related LinksTop of the: day, week, month.

Repel them. Repel them. Induce them to relinquish the spheroid. - Indiana University fans' chant for their perennially bad football team

Working...