×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Possible Issues With the P != NP Proof

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

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

cancel ×
This is a preview of your comment

No Comment Title Entered

Anonymous Coward 1 minute ago

No Comment Entered

147 comments

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)

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

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

Fails at step 3.

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)

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:How? (1)

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

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

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)

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?

Re:Incompleteness (1)

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

No, it fail at step 2: Step 1. Post that a P != NP Proof as issues Step 2. ??? Step 3. Profit

Re:Incompleteness (1)

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

In addition to the fail at step 3 mentioned in sibling thread, step 6 does not follow. Math might be incomplete in other areas, and be complete in all that is needed to state P=NP.

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.

Hopefully, this is also self-evident.

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

Couple of things: Irrespective of whether P = NP or not, there exists polynomial-time reductions [wikipedia.org] 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 [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 not show 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.

Algorithms (-1)

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

All of this goes so over my head I can't even deploy enough air defense.

Re:Algorithms (1)

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

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.

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)

If you think 'polynomial time' and 'quickly' are in any way similar, there's a good chance that you're a theoretical computer scientist.

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)

I haven't been this confused since reading Godel's Proof.

Re:What? (0, Offtopic)

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

for whomever modded this down - you are are fool. Just read the comment above entitled incompleteness. Its completely related and NOT off topic. Its exactly whats going on here... so particularly, you are dead wrong in your assessment of me being off topic.

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

Affenkopf (949241) | more than 3 years ago | (#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 (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)

I suppose the OP but he could choose to share a part of the money to show fair play.

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)

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

Re:Publication Bias (4, Funny)

martin-boundary (547041) | more than 3 years ago | (#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: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 is mathematics, 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)

It includes Computer Architecture, Software Engineering, and other topics that...

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)

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

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)

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 complexity theory contains the answer to all mathematical problems, which is exactly why (in a very tangible sense for those familiar with the attempts at the problem including approaches based on circuit complexity) the problem P ?= NP is so hard to solve.

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

I'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)

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 background knowledge.
    Field: Physics.
    Geek score: 3
  • Pre-big bang universe: Requires a fair amount of ignorance and faith.
    Field: Religion.
    Geek score: -5
  • Phone company math: Requires average intelligence, but understanding how people want to be scammed.
    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)

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

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

feel very very stupid after reading that.

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

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

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

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

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

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

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

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

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)

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

fr@ist6 stop (-1, Troll)

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

fun to be again. BE NIIGER! BE GAY! America. You, my caaling. Now I backward and said Why not? It's quick hobbyist dilettante

What would be better? (3, Interesting)

2obvious4u (871996) | more than 3 years ago | (#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: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.

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!

Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...