Beta
×

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 about 4 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 ×

147 comments

Sorry! There are no comments related to the filter you selected.

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

grepya (67436) | about 4 years ago | (#33212518)

...

uh... (-1, Offtopic)

madddddddddd (1710534) | about 4 years ago | (#33212522)

NP has an N... case closed.

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

Comboman (895500) | about 4 years ago | (#33213916)

But if N = 1 then P = NP

for all other values of N then P != NP

Re:uh... (0)

Anonymous Coward | about 4 years ago | (#33214474)

P=NP when P=0 as well.

Re:uh... (0)

Anonymous Coward | about 4 years ago | (#33214480)

Unless P=0. Duh.

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

Anonymous Coward | about 4 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) | about 4 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) | about 4 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) | about 4 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) | about 4 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)

Omnifarious (11933) | about 4 years ago | (#33213890)

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

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

mentaldrano (674767) | about 4 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) | about 4 years ago | (#33215310)

Oh for mod points. That was brilliant.

Re:Incompleteness (1, Interesting)

Anonymous Coward | about 4 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) | about 4 years ago | (#33212974)

Fails at step 3.

How? (0)

Anonymous Coward | about 4 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) | about 4 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) | about 4 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 | about 4 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 | about 4 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) | about 4 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) | about 4 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) | about 4 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) | about 4 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) | about 4 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 | about 4 years ago | (#33216386)

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

Re:Incompleteness (2)

david_thornley (598059) | about 4 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:Incompleteness (0)

Anonymous Coward | about 4 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) | about 4 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) | about 4 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 | about 4 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) | about 4 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) | about 4 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) | about 4 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) | about 4 years ago | (#33212594)

Possible != Not Possible

Proof enough for me.

Algorithms (-1)

Terranex (1500465) | about 4 years ago | (#33212602)

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

Re:Algorithms (1)

carlzum (832868) | about 4 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 | about 4 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 | about 4 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) | about 4 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 | about 4 years ago | (#33215188)

:D true

What? (1, Interesting)

lawnboy5-O (772026) | about 4 years ago | (#33212634)

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

Re:What? (0, Offtopic)

lawnboy5-O (772026) | about 4 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 | about 4 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 | about 4 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 | about 4 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) | about 4 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) | about 4 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) | about 4 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) | about 4 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) | about 4 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 | about 4 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) | about 4 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) | about 4 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 | about 4 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) | about 4 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) | about 4 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) | about 4 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) | about 4 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 | about 4 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 | about 4 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) | about 4 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) | about 4 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) | about 4 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 | about 4 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) | about 4 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) | about 4 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) | about 4 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) | about 4 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) | about 4 years ago | (#33212786)

feel very very stupid after reading that.

Re:I for one (0)

Anonymous Coward | about 4 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 | about 4 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) | about 4 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) | about 4 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 | about 4 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) | about 4 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) | about 4 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) | about 4 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 | about 4 years ago | (#33212788)

Come on.

Hard core (5, Interesting)

gregrah (1605707) | about 4 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) | about 4 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) | about 4 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) | about 4 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 | about 4 years ago | (#33215518)

My touring machine is a Surly Long Haul Trucker

It looks like (2, Insightful)

maroberts (15852) | about 4 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) | about 4 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) | about 4 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 | about 4 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) | about 4 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) | about 4 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.

Re:Dick Lipton (1)

shadowofwind (1209890) | about 4 years ago | (#33215274)

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

Re:Dick Lipton (1)

Bigjeff5 (1143585) | about 4 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 | about 4 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) | about 4 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) | about 4 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) | about 4 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) | about 4 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) | about 4 years ago | (#33215144)

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

A Layman's Take (1)

necro351 (593591) | about 4 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 | about 4 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 Login

Need an Account?

Forgot your password?

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>