# Possible Issues With the P != NP Proof

#### Soulskill posted more than 3 years ago | from the intuitively-obvious-to-the-most-casual-observer dept.

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

## you don't say... (-1, Offtopic)

## grepya (67436) | more than 3 years ago | (#33212518)

...

## uh... (-1, Offtopic)

## madddddddddd (1710534) | more than 3 years ago | (#33212522)

NP has an N... case closed.

## Re:uh... (-1, Offtopic)

## Comboman (895500) | more than 3 years ago | (#33213916)

for all other values of N then P != NP

## Re:uh... (0)

## Anonymous Coward | more than 3 years ago | (#33214474)

P=NP when P=0 as well.

## Re:uh... (0)

## Anonymous Coward | more than 3 years ago | (#33214480)

Unless P=0. Duh.

## Proof that a proof can't exist? (0)

## Anonymous Coward | more than 3 years ago | (#33212532)

Has anyone attempted to prove that you can't prove whether or not P == NP?

At this point I see that being about as likely as actually proving whether or not P == NP.

## Re:Proof that a proof can't exist? (0, Troll)

## madddddddddd (1710534) | more than 3 years ago | (#33212554)

well... in that case you would be proving that if the proof could exist something else must exist that can be proven to never exist if the proof could exist.

time is better spent on a O(log(n)) or better prime generating function

## Incompleteness (5, Interesting)

## im_thatoneguy (819432) | more than 3 years ago | (#33212642)

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 [wikipedia.org]

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.

## Yes, they've tried that (5, Informative)

## Xenographic (557057) | more than 3 years ago | (#33212732)

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 [wordpress.com] 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 (5, Funny)

## nomoreunusednickname (1471615) | more than 3 years ago | (#33212892)

## Re:Yes, they've tried that (1)

## Omnifarious (11933) | more than 3 years ago | (#33213890)

This deserves +5 funny if any comment on this thread does.

## Re:Yes, they've tried that (1)

## mentaldrano (674767) | more than 3 years ago | (#33214686)

I have discovered a truly marvelous proof that P != NP, but this comment is not rated highly enough to contain it.

## Re:Yes, they've tried that (1)

## Fross (83754) | more than 3 years ago | (#33215310)

Oh for mod points. That was brilliant.

## Re:Incompleteness (1, Interesting)

## Anonymous Coward | more than 3 years ago | (#33212856)

Here's a proof short enough to reproduce in a comment. http://www.win.tue.nl/~gwoegi/P-versus-NP/argall.txt [win.tue.nl]

P=NP - An impossible question

A proposed proof of undecidability by Nicholas Argall, 25 March, 2003.

There has been much debate surrounding answers to the question of P=NP.

The problem is that we cannot answer the question until we have successfully

asked the question. The question is impossible to ask, that it why it will

never be answered.

1) A provable answer to the question P=NP requires a complete and consistent

formal statement of the question.

Rationale: Hopefully, this is self-evident. It is certainly axiomatic that

a formally provable statement be expressed in formal terms. Completion and

consistency follow from the requirement to provide a proof that is not

subject to challenge.

2) A complete and consistent formal statement of the question must

incorporate a complete and consistent formal definition of the sets P and NP

Rationale: Hopefully, this is also self-evident. (I have left out the

requirement to define the equality operator, since it is defined for us by

set theory.)

3) A definition based on a potentially undetectable characteristic is

incomplete

Rationale: We cannot accept the definition of the set NP purely in terms of

its members having a property (a solution test in polynomial time) that we

have no reliable mechanism to detect. Therefore, a complete definition of

the set NP must be arrived at via some other means.

4) The only possibility for a complete definition of the set NP is a

language

Rationale: Once we rule out observation of characteristics, our only means

towards a definition of the set NP is to formulate a language, a procedure

for testing the formal expression of the candidate problem that will accept

the problem or reject it.

5) No formal language capable of expressing non-trivial mathematical

problems can be consistent and complete

Rationale: As proven by Godel.

6) Therefore, no consistent and complete definition of the set NP is possible

Rationale: If we accept that the set NP can only be rigorously defined via a

language, this conclusion follows from the premises above.

7) Therefore, no consistent and complete statement of the problem of P=NP is

possible

Comment: A conclusion which is not only proven in this paper, but supported

by the years of argument between mathematicians regarding the relevance of

proposed answers to the problem.

8) Therefore, P=NP is undecidable

Comment: Given our inability to ask, we are unable to answer.

## Re:Incompleteness (4, Insightful)

## digitig (1056110) | more than 3 years ago | (#33212974)

## How? (0)

## Anonymous Coward | more than 3 years ago | (#33212990)

No it doesn't.

See, I can make bald faced assertions with nothing to back them up too!

## Re:How? (5, Informative)

## digitig (1056110) | more than 3 years ago | (#33213038)

definition, not any means of actuallydetectingcases. Look at pretty much any proof involving transfinites.## Re:How? (1)

## esrobinson (1028500) | more than 3 years ago | (#33213142)

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

## Re:How? (0)

## Anonymous Coward | more than 3 years ago | (#33213270)

True, there are a lot of theorems that something exists not giving any means to detect what it is (and all of them proven).

## Re:How? (0)

## Anonymous Coward | more than 3 years ago | (#33213490)

Youre confusing theorems and axioms. Transfinites use undetectable axioms, and that's fine, but P is not an axiom but a theorem constructed in an axiomatic paradigm. Undetectable theorems are a problem that axioms don't have.

## Re:How? (1)

## digitig (1056110) | more than 3 years ago | (#33213616)

## Re:Incompleteness (1)

## davrob60 (1689994) | more than 3 years ago | (#33214304)

## Re:Incompleteness (1)

## sFurbo (1361249) | more than 3 years ago | (#33213488)

That there is a problem should be evident from the fact that this proof doesn't use any specifics of P=NP, so it can be used to prove anything undecidable, which is clearly wrong, since there exist proven theorems.

## Re:Incompleteness (1)

## Magada (741361) | more than 3 years ago | (#33214568)

3) sounds very much like the objections of early mathematicians when they had to deal with prime numbers. "there isn't a function that generates all the possible primes, so how can we work with them?"

## Re:Incompleteness (1)

## russotto (537200) | more than 3 years ago | (#33215522)

How could P=NP be proven undecidable? If P=NP is proven undecidable, it means there can be no deterministic polynomial-time algorithm to solve an NP-complete problem in polynomial time (because such an algorithm would prove that P=NP). If no such algorithm exists, then P!=NP.

(this doesn't mean P=NP can't be undecidable... it just means that if if it is undecidable, the question of its undecidability is also so, and so on up the line)

## Re:Incompleteness (0)

## Anonymous Coward | more than 3 years ago | (#33216386)

There could be a polynomial-time algorithm which cannot be proven to be polynomial-time.

## Re:Incompleteness (2)

## david_thornley (598059) | more than 3 years ago | (#33216012)

If, in step 2, you mean a formal decision procedure to tell if an problem is in P or in NP, no, we don't. We know that any problem in P is also in NP, by definition. Therefore, if we can prove that any problem in NP is also in P, using only properties we've proved belong to NP, we've got a proof. If we can prove that any individual problem in NP is not in P, we have a proof of the opposite. Neither of these requires a general NP- or P-detector.

Technically, we could possibly have a proof one way or another without knowing any problem in P or NP.

Demons and other evil things lurk in statements like this. Either it is clearly self-evident, or it shows that you haven't thought things through. In step 1, it is self-evident that a formal proof demands a formal statement of what is to be proved. In step 2, you simply haven't thought well enough about what a proof needs.

## Re:Incompleteness (0)

## Anonymous Coward | more than 3 years ago | (#33212910)

That's a long article. Here's the relevant section [wikipedia.org] .

## Re:Proof that a proof can't exist? (0)

## chichilalescu (1647065) | more than 3 years ago | (#33212706)

I almost modded you interesting, but I can't.

I don't have enough of a background to realize if, for the particular issue of P (!)= NP, it makes sense to think of decidability. I do suspect it doesn't, because the problem is pretty old, and I've never heard of anyone talking about its decidability.

When there's a million dollars involved, I've learned to expect that enough people tried enough different ways to exhaust all the ideas I can have in 5 minutes from hearing about the problem (and ever since I've heard of the axiom of choice, I've thought that maybe some interesting questions are about undecidable problems).

## Re:Proof that a proof can't exist? (1)

## locofungus (179280) | more than 3 years ago | (#33212758)

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

## Re:Proof that a proof can't exist? (0)

## Anonymous Coward | more than 3 years ago | (#33212796)

The only loophole I can see is that the algorithm could exist but could not be proven to run in polynomial time

Wikipedia mentions an algorithm proven to solve NP complete problems in P if and only if P = NP [wikipedia.org] .

## Re:Proof that a proof can't exist? (2)

## gphilip (1155691) | more than 3 years ago | (#33213486)

I am not sure in what sense you use the term "undecidable", but if (as it seems likely) you used it to mean independent [wikipedia.org] , 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

notshow that no polynomial-time reduction exists from from any NP-complete problem to any problem in P.In other words, undecidable != false.

## Re:Proof that a proof can't exist? (3, Informative)

## FrangoAssado (561740) | more than 3 years ago | (#33212988)

This question has been considered by quite a few different people; search google for P vs NP independent [google.com] ("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? [scottaaronson.com] .

## Re:Proof that a proof can't exist? (3, Insightful)

## UnknowingFool (672806) | more than 3 years ago | (#33215574)

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.

## Proof (0, Offtopic)

## fluor2 (242824) | more than 3 years ago | (#33212594)

Possible != Not Possible

Proof enough for me.

## Algorithms (-1)

## Terranex (1500465) | more than 3 years ago | (#33212602)

## Re:Algorithms (1)

## carlzum (832868) | more than 3 years ago | (#33212672)

## Re:Algorithms (3, Interesting)

## Anonymous Coward | more than 3 years ago | (#33213356)

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

## Re:Algorithms (1, Interesting)

## Anonymous Coward | more than 3 years ago | (#33213466)

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

## Re:Algorithms (2, Funny)

## TheRaven64 (641858) | more than 3 years ago | (#33214454)

## Re:Algorithms (0)

## Anonymous Coward | more than 3 years ago | (#33215188)

:D true

## What? (1, Interesting)

## lawnboy5-O (772026) | more than 3 years ago | (#33212634)

## Re:What? (0, Offtopic)

## lawnboy5-O (772026) | more than 3 years ago | (#33212674)

## Re:What? (0)

## Anonymous Coward | more than 3 years ago | (#33212836)

True, your original post is definitely not off topic, rather the opposite. But it's not exactly contributing a lot to the discussion either. The link between P(!)=NP and Goedel has been made several times (although so far nobody has come with a watertight reasoning why this would "resolve" the issue). So what if you've been confused...

Posting anonymously in order not to undo the many mods I already did in this discussion.

## Re:What? (-1, Flamebait)

## Anonymous Coward | more than 3 years ago | (#33212860)

I'm sure even the editors have no idea what this article is about, either. They probably posted it because it has more technobabble than a bad ST:NG episode and they've met their Apple story quota for the day.

## Re:What? (0)

## Anonymous Coward | more than 3 years ago | (#33212952)

Now I'll never know if the mod I pissed off was a math nerd, a trekkie or an Apple fanboy. Any more sacred cows to BBQ?

## Current Status (5, Informative)

## pdxp (1213906) | more than 3 years ago | (#33212654)

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 (5, Funny)

## Affenkopf (949241) | more than 3 years ago | (#33212900)

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

## Mathematicians are gathering to vet this paper (5, Informative)

## Xenographic (557057) | more than 3 years ago | (#33212680)

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:Mathematicians are gathering to vet this paper (1)

## JohnFluxx (413620) | more than 3 years ago | (#33212768)

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

## Re:Mathematicians are gathering to vet this paper (1)

## hvm2hvm (1208954) | more than 3 years ago | (#33212896)

## Re:Mathematicians are gathering to vet this paper (1, Insightful)

## Anonymous Coward | more than 3 years ago | (#33212784)

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.

## Publication Bias (5, Funny)

## mSparks43 (757109) | more than 3 years ago | (#33212806)

## Re:Publication Bias (4, Funny)

## martin-boundary (547041) | more than 3 years ago | (#33213070)

## Re:Publication Bias (0)

## Anonymous Coward | more than 3 years ago | (#33213394)

Better make it a nonconstructive proof!

(Or put the constructive proof inside

insurance.aes256)## Re:Mathematicians are gathering to vet this paper (0, Troll)

## yyxx (1812612) | more than 3 years ago | (#33213796)

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

## Re:Mathematicians are gathering to vet this paper (1)

## PeterBrett (780946) | more than 3 years ago | (#33214264)

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

But computer science

ismathematics, or rather a subset thereof.## Re:Mathematicians are gathering to vet this paper (0, Troll)

## yyxx (1812612) | more than 3 years ago | (#33214596)

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 and irrelevant as saying "mammals are gathering to vet this paper".

## Re:Mathematicians are gathering to vet this paper (4, Insightful)

## silentcoder (1241496) | more than 3 years ago | (#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:Mathematicians are gathering to vet this paper (0)

## Anonymous Coward | more than 3 years ago | (#33215646)

You seem to be forgetting that Computer Science is not just "Theory of Computation". It includes Computer Architecture, Software Engineering, and other topics that mathematicians don't care for.

## Re:Mathematicians are gathering to vet this paper (0)

## Anonymous Coward | more than 3 years ago | (#33215990)

None of those are sciences. Most of what people consider CS are social practices for the people that work together to make and use the machines.

## Re:Mathematicians are gathering to vet this paper (0)

## judo_badger (812451) | more than 3 years ago | (#33215772)

## Re:Mathematicians are gathering to vet this paper (2, Funny)

## PachmanP (881352) | more than 3 years ago | (#33216278)

Strictly speaking, every computer in the real world is a finite state machine that's complex enough to simulate a universal Turing machine. It's a subtle difference that really only matters if you're considering the math behind it ;)

Oh Snap!!

## Re:Mathematicians are gathering to vet this paper (1)

## paradigm82 (959074) | more than 3 years ago | (#33215782)

## Re:Mathematicians are gathering to vet this paper (0)

## Anonymous Coward | more than 3 years ago | (#33216190)

"multi-CPU machines are actually EASIER to program for in a functional language like lisp"

Yes, but writing a Lisp interpreter (or compiler) that can use multiple CPUs effectively is no small task.

## Re:Mathematicians are gathering to vet this paper (1)

## Chris Burke (6130) | more than 3 years ago | (#33216228)

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 only recognize math if it is syntactically nearly identical to the math they would do with a pencil and paper. And it's a fine comparison to make, but as I'm sure you know it's not necessary.

For folks who deal with computers at a lower level and aren't confused by divergent syntax, consider a computer ISA.

An ISA is really just a description of a bunch of valid mathematical operators and the operations they perform. There's no reason that the ISA requires hardware that directly implements that ISA, or for that matter a computer of any kind, as long as the math is faithfully performed. That's what makes simulators like Simnow [amd.com] possible, because everything a computer does is just math and can be translated into any equivalent math and you'll get the same result. Even including the IO, since even the behavior of the hard drive, at least as it appears to a program, is simply a mathematical operation.

It's true that currently the most popular languages do not follow the lisp "look like the function you are" structureI'm not sure I follow you there... the mathematical operations that comprise a function is the function it is, and nothing looks more like that than the underlying assembly. I do get the advantages of functional programming for multithreaded programming, just not sure what you're saying there.

## This and... (1)

## Powercntrl (458442) | more than 3 years ago | (#33212698)

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:This and... (1)

## arth1 (260657) | more than 3 years ago | (#33213694)

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

Field: Computers.

Geek score: 1

Field: Physics.

Geek score: 3

Field: Religion.

Geek score: -5

Field: Psychology.

Geek score: 2

The P != NP problem, however, is pure math. You have to have some skills in the field to understand what the problem is, and as it's hard to break it down to a simple non-abstract that even journalists can understand, it won't be mainstream unless it can be blessed with a catchier name and background story (like Fermat's Last Theorem, which many people have heard of, but of which few have any kind of idea what the theorem itself was about).

Field: Mathematics

Geek score: 5

## Re:This and... (1)

## Antisyzygy (1495469) | more than 3 years ago | (#33214614)

## I for one (5, Funny)

## Chuck Chunder (21021) | more than 3 years ago | (#33212786)

## Re:I for one (0)

## Anonymous Coward | more than 3 years ago | (#33213410)

His follow on is a little easier to understand (at a high level), but there's still some gems such as

"However, this would also bring the Razborov-Rudich barrier into play, which the author expressly references and must avoid."

Which I assume must be some mathematical equivalent of crossing the beams.

## Re:I for one (0)

## Anonymous Coward | more than 3 years ago | (#33213542)

I think I understand the proof that Microsoft gave back in 1990 that SS != DS for 16-bit Windows.

## Re:I for one (1, Funny)

## Anne_Nonymous (313852) | more than 3 years ago | (#33213660)

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:I for one (1)

## Anne_Nonymous (313852) | more than 3 years ago | (#33213704)

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:I for one (0)

## Anonymous Coward | more than 3 years ago | (#33214750)

This was redundant even before you posted it a second time. The joke does get old.

## Re:I for one (2, Insightful)

## Bigjeff5 (1143585) | more than 3 years ago | (#33216406)

NP has an N in it

So it's not the same as P

Prove it.

## Re:I for one (1)

## Omnifarious (11933) | more than 3 years ago | (#33213934)

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

## Re:I for one (1)

## Bigjeff5 (1143585) | more than 3 years ago | (#33216422)

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

## Dick Lipton? (0)

## Anonymous Coward | more than 3 years ago | (#33212788)

Come on.

## Hard core (5, Interesting)

## gregrah (1605707) | more than 3 years ago | (#33212810)

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 (5, Funny)

## tehcyder (746570) | more than 3 years ago | (#33212958)

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

## Re:Hard core (1)

## tyrione (134248) | more than 3 years ago | (#33213170)

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:Hard core (1)

## akirapill (1137883) | more than 3 years ago | (#33214746)

## Re:Hard core (0)

## Anonymous Coward | more than 3 years ago | (#33215518)

My touring machine is a Surly Long Haul Trucker

## It looks like (2, Insightful)

## maroberts (15852) | more than 3 years ago | (#33212968)

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 (3, Insightful)

## PeterM from Berkeley (15510) | more than 3 years ago | (#33214776)

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:It looks like (1)

## iris-n (1276146) | more than 3 years ago | (#33215102)

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.

## My Proof (0)

## Anonymous Coward | more than 3 years ago | (#33213248)

1. The axioms of mathematics

2. ?????????????

3. P!=NP

I just need to fill in one small hole.

## Okay honestly ... (1)

## tgd (2822) | more than 3 years ago | (#33213674)

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 (3, Informative)

## Sara Chan (138144) | more than 3 years ago | (#33213754)

## Re:Dick Lipton (1)

## shadowofwind (1209890) | more than 3 years ago | (#33215274)

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

## Re:Dick Lipton (1)

## Bigjeff5 (1143585) | more than 3 years ago | (#33216460)

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

## fr@ist6 stop (-1, Troll)

## Anonymous Coward | more than 3 years ago | (#33213956)

## What would be better? (3, Interesting)

## 2obvious4u (871996) | more than 3 years ago | (#33214552)

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:What would be better? (2)

## godrik (1287354) | more than 3 years ago | (#33215092)

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

## Problem solving (2, Interesting)

## Fractal Dice (696349) | more than 3 years ago | (#33214648)

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:Problem solving (1)

## Bigjeff5 (1143585) | more than 3 years ago | (#33216500)

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

## Godskitchen (1017786) | more than 3 years ago | (#33215144)

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

## A Layman's Take (1)

## necro351 (593591) | more than 3 years ago | (#33215802)

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 [zdnet.com]

## Its not that difficult.. (0)

## Anonymous Coward | more than 3 years ago | (#33215948)

1 != N, for all N != 1.

Multiplying both sides by P,

P != NP.

If N == 1, then P = NP.

Simple. I am not sure why this is so difficult!