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!

Claimed Proof That P != NP

kdawson posted more than 4 years ago | from the sufficiently-complex dept.

Math 457

morsch writes "Researcher Vinay Deolalikar from HP Labs claims proof that P != NP. The 100-page paper has apparently not been peer-reviewed yet, so feel free to dig in and find some flaws. However, the attempt seems to be quite genuine, and Deolalikar has published papers in the same field in the past. So this may be the real thing. Given that $1M from the Millennium Prize is involved, it will certainly get enough scrutiny. Greg Baker broke the story on his blog, including the email Deolalikar sent around."

cancel ×

457 comments

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

Well, duh (5, Funny)

Anonymous Coward | more than 4 years ago | (#33183704)

I mean, NP has an N in front of the P. That's obviously not the same as P. Also, P != HP.

Re:Well, duh (1, Interesting)

hedwards (940851) | more than 4 years ago | (#33183750)

Well, perhaps N=H=1?

In other news, HP sex Scandal == Push other news (4, Funny)

tomhudson (43916) | more than 4 years ago | (#33184276)

It's funny how we don't hear anything from HP for ages, then as soon as there's a sex scandal involving the disgraced CEO [engadget.com] , out come all sorts of distractions.

I smell a rat. Okay, I smell 2 rats - Mark Hurd (ex-CEO) and HPs' spin department.

Re:Well, duh (5, Funny)

Anonymous Coward | more than 4 years ago | (#33183766)

I mean, NP has an N in front of the P. That's obviously not the same as P. Also, P != HP.

If you knew really advanced mathematics you'd know that NP means N times P. So NP does equal P when N=1. But not the rest of the time. Oh and it does when P=0. How much was that prize again?

Re:Well, duh (5, Informative)

Peach Rings (1782482) | more than 4 years ago | (#33183830)

Ohhhh my god, someone modded this insightful.

P is polynomial time.
NP is non-deterministic polynomial time.
They're algorithmic complexity classes.

Re:Well, duh (4, Insightful)

Anonymous Coward | more than 4 years ago | (#33183884)

Ohhhh my god, someone modded this insightful.

Okay... sometimes when it's really really really obvious that something's a joke, it's okay to play along and make mock serious follow ups and even *gasp* non-serious moderations. This works on the basis that it's obvious that both the original poster and the modder are joking.

Re:Well, duh (4, Funny)

Peach Rings (1782482) | more than 4 years ago | (#33184020)

I had an unshakable image of some web design "IT guy" who had one forgotten lecture on this subject back in trade school nodding sagely as he thinks he understands what everyone's talking about and reaching for the Insightful moderation.

I didn't have the benefit of the reassuring Score:5, Funny that you had.

Re:Well, duh (-1, Troll)

Cylix (55374) | more than 4 years ago | (#33183990)

I don't know if I trust that statement as it seems as if it was created from a techno babble generator.

If "non-deterministic polynomial time" is an actual "algorithmic complexity class' then so is my "anomalous quantum field" which generally intersects with a "temporal phase disturbance."

And now I will return to watching Idiocracy or as I like to call it... the future.

Re:Well, duh (1)

ioshhdflwuegfh (1067182) | more than 4 years ago | (#33184036)

But that's what plants crave!

Re:Well, duh (2, Funny)

PopeRatzo (965947) | more than 4 years ago | (#33184098)

If "non-deterministic polynomial time" is an actual "algorithmic complexity class' then so is my "anomalous quantum field" which generally intersects with a "temporal phase disturbance."

Professor Corey? Is that you, Irwin?

Re:Well, duh (0)

Anonymous Coward | more than 4 years ago | (#33184004)

Hook, line and sinker.

Re:Well, duh (5, Funny)

Draek (916851) | more than 4 years ago | (#33184048)

Funny doesn't give karma, Insightful does.

At least that's what I tell myself so I can sleep at night.

Funny can cost you karma (1, Insightful)

davidwr (791652) | more than 4 years ago | (#33184100)

+1 funny
-1 overated
+1 funny
+1 funny
-1 overated
+1 funny
+1 funny
-1 overated
+1 funny
+1 funny
-1 overated
+1 funny
+1 funny
-1 overated
+1 funny
repeat last 3 lines as many times as you like.

Net result: post is +5 funny but you take major karma hits.

Disclaimer: This was true in the early days of funny = no karma boost. They may have fixed it by now. Personally, I think karma should not contribute to karma except to offset overrated or some similar rating designed to indicate "not as funny as it's currently rated."

Re:Funny can cost you karma (1)

siride (974284) | more than 4 years ago | (#33184186)

karma should not contribute to karma, eh?

Poly? Poly want a cracker? (0)

Anonymous Coward | more than 4 years ago | (#33184118)

Say who/wha/where? We are da linuxers, we don no no maths!!

Re:Well, duh (0, Flamebait)

icebike (68054) | more than 4 years ago | (#33184114)

I mean, NP has an N in front of the P. That's obviously not the same as P. Also, P != HP.

If you knew really advanced mathematics you'd know that NP means N times P. So NP does equal P when N=1. But not the rest of the time. Oh and it does when P=0. How much was that prize again?

And if you didn't know any advanced mathematics You could read the wiki page about this problem:

http://en.wikipedia.org/wiki/P_versus_NP_problem [wikipedia.org]

However, it seems you could read that page, and still have not a single useable clue.

Rats! (0)

5pp000 (873881) | more than 4 years ago | (#33183720)

I was right on the edge of solving it myself.

Not :-)

Well, Thank God... (5, Funny)

jjohnson (62583) | more than 4 years ago | (#33183730)

I am pleased to announce a proof that P is not equal to NP, which is attached in 10pt and 12pt fonts.

I was a afraid he might have left out an important step.

Re:Well, Thank God... (3, Funny)

ArsonSmith (13997) | more than 4 years ago | (#33183804)

it was shortened the original proof he was working on was 10Pt !=(or Not) 12Pt font. The journalist shortened it to P!=NP. The rest of the text is meaningless other than to illustrate the difference.

Re:Well, Thank God... (0, Offtopic)

Twinbee (767046) | more than 4 years ago | (#33183948)

Just gonna moan about your sig, sorry. If by definition, one language is simpler, more elegant, faster yet also slightly more high level, terser, yet more powerful than another programming language, that would make it 'better' than another language given all else equal. If we accept that a language could be slightly better than another language then it stands to reason that a language could be *much* better (or indeed, much worse).

I don't really currently like or hate any language (I use c/c++ mostly, if only for the speed) as they all have their glaring faults. But in theory, and maybe in practise within 100 years, a language will be so good that it deserves to be loved, and yes, loved more so than other languages.

Re:Well, Thank God... (0)

Anonymous Coward | more than 4 years ago | (#33184152)

I'll give you this: you did prove his sig lacking. It should just say "anyone talking about any language, platform, or manufacturer doesn't know what they're talking about."

this is going to create history (0)

Anonymous Coward | more than 4 years ago | (#33183740)

this is going to create history

Re:this is going to create history (1)

Peach Rings (1782482) | more than 4 years ago | (#33183860)

FLT took over three hundred sixty years to prove, and so far P=NP appears to be even slipperier. The whole field of study is only 40 years old too.

Re:this is going to create history (1)

icannotthinkofaname (1480543) | more than 4 years ago | (#33183910)

It's only going to create history if there is no flaw in the proof. If Deolalikar missed something, then this is all hype.

Simpletons! (0)

hansamurai (907719) | more than 4 years ago | (#33183752)

For values of N where N != 1

Re:Simpletons! (1)

hkz (1266066) | more than 4 years ago | (#33183858)

And P is nonzero.

I think this is going to take a while. (1)

IgnitusBoyone (840214) | more than 4 years ago | (#33183754)

At a 100 pages its going to be a while before I can say I have RTFA, but I'll get back with any relevance in a few days after I have digested it. I suggest any post claiming other wise are a bit hasty.

Not Only Time But Several Disciplines (4, Interesting)

eldavojohn (898314) | more than 4 years ago | (#33183838)

At a 100 pages its going to be a while before I can say I have RTFA, but I'll get back with any relevance in a few days after I have digested it. I suggest any post claiming other wise are a bit hasty.

You can read section one (the introduction) and get a high level walk through of what he's doing. Just be prepared to have a requisite in the following to make it through that:

In order to apply this analysis to the space of solutions of random constraint satisfaction problems, we utilize and expand upon ideas from several fields spanning logic, statistics, graphical models, random ensembles, and statistical physics.

My computer science, math and statistics are still fairly sharp but the physics and graph theory are a bit much. Indeed this will take a while to digest. If he hasn't made a mistake in something like bridging together least fixed point logic and functions [wikipedia.org] with Markov-Gibbs properties (correspondence and equivalence) [ia.ac.cn] .

On the one hand it seems this will take a general expert in the math related sciences to verify but on the other you would think that -- like with the E8 and Lie groups -- this sort of proof would require a rather large unified theory to be able to reduce the N=NP? problem down to a provable situation. I'm no expert and it's been three or four years since I've even been in academia but even the subsections of this paper are noteworthy if they are true. It could be we're looking at something that jumps so far ahead like the famous papers of Turing and Shannon.

Re:I think this is going to take a while. (2, Funny)

Niobe (941496) | more than 4 years ago | (#33184016)

At a 100 pages its going to be a while before I can say I have RTFA, but I'll get back with any relevance in a few days after I have digested it. I suggest any post claiming other wise are a bit hasty.

Aren't the best theories supposed to be elegantly simple? This looks a mess.
Wait.. that's just how my head feels after reading the abstract.

Re:I think this is going to take a while. (0)

Anonymous Coward | more than 4 years ago | (#33184204)

Depends, the 4-color Theorem still requires computer aided proof.

Well, shoulders of giants and all (1, Insightful)

Anonymous Coward | more than 4 years ago | (#33183762)

As far as I know, this is the first very public proof attempt- its likely it will have flaws, but it may pave the way for someone else or further attempts from the same source even if flaws are found.

Let me be the first to say (1)

Zaphod The 42nd (1205578) | more than 4 years ago | (#33183764)

OH YEAH!!!!!

How dare you say "OH YEAH!!!!!" (3, Funny)

Anonymous Coward | more than 4 years ago | (#33183844)

The C&D letter is in the mail, buster. -Kool-Aid Man

Re:How dare you say "OH YEAH!!!!!" (1)

EmagGeek (574360) | more than 4 years ago | (#33184106)

Whatchoo talkin' about, AC????

What would the impacts of this be for cryptography (3, Interesting)

HungryHobo (1314109) | more than 4 years ago | (#33183770)

What would the impacts of this be for cryptography?
from a theoretical point of view at least?

I was under the impression that a lot of cryptography was based upon the hope that P!=NP and while in practice this wouldn't change much about anyone acts it might have an impact on how people think about the old cryptology vs cryptanalysis race.

Re:What would the impacts of this be for cryptogra (4, Informative)

jjohnson (62583) | more than 4 years ago | (#33183796)

Off the top of my head, if P = NP, then a lot of cryptography like RSA and elliptic curve cryptography become, in principle, mathematically solvable. Much of their security is premised on the idea that their equations are prohibitively difficult to brute force because they're NP.

If this proof holds up, then RSA and ECC become provably secure in a way they weren't before.

Re:What would the impacts of this be for cryptogra (1, Informative)

Anonymous Coward | more than 4 years ago | (#33183928)

My analysis said DH would hold even if P=NP.

I had a lower bound on the order of the polynomial for breaking DH and it was something like 256. There's really not much practical difference between n256n for n = 4096. Both are practically intractable.

Re:What would the impacts of this be for cryptogra (1)

Peach Rings (1782482) | more than 4 years ago | (#33183940)

No. Even if there are found to be integer factorization algorithms theoretically in P, there's still no practical way to crack it. This is all asymptotic complexity (what happens as your key size goes to infinity), which might be important when we start using tebibit symmetric keys, but in the real world the constant coefficients (which are thrown away in asymptotic analysis) would be really high.

Elliptic curve crypto is different though, I think.

Re:What would the impacts of this be for cryptogra (2, Informative)

Peach Rings (1782482) | more than 4 years ago | (#33183962)

I meant asymmetric, which is what RSA is. Symmetric keys are usually exchanged relying on the discrete logarithm problem (RSA problem [wikimedia.org] ), not the integer factorization problem.

Re:What would the impacts of this be for cryptogra (0)

Anonymous Coward | more than 4 years ago | (#33183984)

Well, just because something is in "P" doesn't mean it's trivial. For instance, if you discovered a prime number factorization algorithm that was O(b^100) it would not be useful for an RSA attack.

Also, it's not even known that factoring primes is NP-complete, co-NP, or even P. It's known to be P in a quantum computer (O(b^3), to be precise) and *suspected* to be not P in a Turing machine, but I don't think anyone has proven that.

Now I know you said "in principle, mathematically solvable".. but by that standard RSA is already solvable. It just isn't known to be solvable quickly. P=NP would not change that.

But all of this is moot since the alleged proof is that P!=NP which is what almost everybody assumed already. So the practical impact of this proof would be minimal, but it still would be a milestone in mathematics. At this stage I'd recommend caution though, there have been many "proofs" for P=NP and P!=NP over the years. This one has a pretty decent pedigree, but it's still very early in the review process. It's very possible that a subtle flaw will be found.

Re:What would the impacts of this be for cryptogra (2, Informative)

kenryd (1727522) | more than 4 years ago | (#33184094)

Off the top of my head, if P = NP, then a lot of cryptography like RSA and elliptic curve cryptography become, in principle, mathematically solvable. Much of their security is premised on the idea that their equations are prohibitively difficult to brute force because they're NP.

If this proof holds up, then RSA and ECC become provably secure in a way they weren't before.

The security of RSA is based on the idea that it is very difficult to factor large integers. However, this has not been shown to be an NP-hard problem and so really doesn't have anything to do with this.

Re:What would the impacts of this be for cryptogra (1)

mdmkolbe (944892) | more than 4 years ago | (#33184144)

I thought RSA might still be P even if P!=NP because we don't know if integer factorization is NP complete.

Re:What would the impacts of this be for cryptogra (1, Insightful)

Anonymous Coward | more than 4 years ago | (#33184224)

It's not. Although it might be NP-hard.

Re:What would the impacts of this be for cryptogra (0)

Anonymous Coward | more than 4 years ago | (#33184160)

No, that's wrong.

P, NP and NP-hardness are properties of *classes* of problems, and they say something on how fast (or slowly) the problems in the class get harder as size of the problem increases.

If a class is NP-hard and NP != P then this class is not P, yes. But it may still be easy for any instance under a billion bits, which would make it easy for practical purposes.

So even if ECC is NP-complete (NP and NP-hard, and I'm really not sure if we know that this is the case), and even if TFA is Tantalizingly Fucking Accurate, this alone doesn't prove the security of any specific system. Although, in practice, in the case of ECC, I'm sure you can count on it.

As for RSA, it's not known to be NP-hard, but again this doesn't rule it out as practically a very secure system.

Re:What would the impacts of this be for cryptogra (4, Interesting)

Zaphod The 42nd (1205578) | more than 4 years ago | (#33183820)

Really, P = NP would have far reaching implications to security, essentially proving that method of security will never be secure. If it is P != NP, then that means that you can have problems which take longer than polynomial time to calculate but only polynomial time to verify. So, if the paper is true, then it doesn't really change a whole lot, except that now we know that some day there isn't going to be a trivial solution. I guess its good for cryptography.

Re:What would the impacts of this be for cryptogra (1, Interesting)

Anonymous Coward | more than 4 years ago | (#33183960)

Really, P = NP would have far reaching implications to security, essentially proving that method of security will never be secure.

Wrong.

1. Polynomials can sill be really big. n^100000000 is in P, but an O(n^100000000) algorithm would not be practical.
2. There are complexity classes above NP which are provably not equivalent to P.

Re:What would the impacts of this be for cryptogra (1)

maraist (68387) | more than 4 years ago | (#33184218)

err.. rainbow tables?? Encryption with O(n ^ inf) of all 10 byte input files are pretty much constant to decrypt, even without the decryption key.

And I'm not sure what you're saying with n^1E8 . Consider what it would mean to have such a coefficient. 100 million nested loops?? Where practically speaking are you going to have that kind of coefficient in a polynomial algorithm? (I only bring it up because you mentioned practical).

The practical problem class is factorial or exponential n ^ x, which occur in combinatorial problem sets (meaning with every new element, you have to consider every existing element's permutations or combinations). Most interesting problems live here.

That being said, I've never formally studied P/NP, and personally find it a boring subject (especially given how much face time the subject gets)

Re:I guess its good for cryptography. (1)

snikulin (889460) | more than 4 years ago | (#33184052)

And it's bad for the rest of us the mere mortals who is sweating optimizing some mundane algorithms to allow them run on slow but power-efficient ARMs of today.

Re:I guess its good for cryptography. (1)

Zaphod The 42nd (1205578) | more than 4 years ago | (#33184142)

Yeah, in some ways it seems disappointing. But at least everything isn't broken! XD

Re:I guess its good for cryptography. (1)

maraist (68387) | more than 4 years ago | (#33184238)

Naah.. Just pass the responsibility over to the hardware guys.. That's what cell phone dudes have been doing for a decade. ;)

Re:What would the impacts of this be for cryptogra (5, Insightful)

Kjella (173770) | more than 4 years ago | (#33184168)

Really, P = NP would have far reaching implications to security, essentially proving that method of security will never be secure. If it is P != NP, then that means that you can have problems which take longer than polynomial time to calculate but only polynomial time to verify.

I think it's important to realize that even if they are "unresolved problems" of mathematics, it's not like both answers are equally likely like the flip of a coin. For example the Riemann hypothesis states that all non-trivial zeros of the Riemann zeta function have real part 1/2. It's true for every non-trivial zero we've ever found, but it's not proven true for all the infinitely many zeros. However, outside of mathematics a proof it's true will be met with "yeah, that's what we thought" and a proof it's false with "OMG what's going on here?". Another example is the prime twin conjecture, are there inifinte pairs like (3,5) (5,7) (11,13) (17,19) and so on. There's very good reason to believe it's true but nobody has able to formally prove it. There's a lot of problems today that appear to support the idea that P != NP, and that's what most people believe the answer is. However, stringing together formal proof that it's so is much harder. If this paper turns out to be true, surely it's a great leap for mathematics but it's the answer that doesn't change the world.

Re:What would the impacts of this be for cryptogra (3, Interesting)

maraist (68387) | more than 4 years ago | (#33184176)

Don't think this is what it means. Look at FFT (logarithmic optimization to a quadratic problem). P = NP as I understand it means that ALL NP problems have a corresponding P solution. You just have to think hard enough to find it. Proving that there are classes of NP that have no P just suggests certain crytographic algorithms MIGHT be NP. But it doesn't prove it (unless it was one of the particularly proven NP classes in this or some other paper). And even if this paper includes RSA / ECC, etc. That doesn't mean someone even more clever 30 years from now finds a flaw or special case where this isn't true and thus finds a P cracking tool.

Re:What would the impacts of this be for cryptogra (0)

mikeee (137160) | more than 4 years ago | (#33183874)

Short form:if P=NP, crypto is something of a futile effort - that implies that there's a non-brute-force crack to every possible private-key algorythm. I suppose it might still be slow enough for the crypto to be useful, but I woudl expect you would end up needing gigantic keys.

Most everybody assumed that P!=NP, but nobody has been able to prove it.

Re:What would the impacts of this be for cryptogra (3, Interesting)

hardburn (141468) | more than 4 years ago | (#33183876)

Practically, not much. It means we can breathe easy that a lot of crypto out there is now provably secure. It's been long considered likely that P != NP, because a lot of NP-complete problems are very old and nobody has gotten very far in solving them, and the extra focus in the last 40 years in breaking public key crypto hasn't produced much more progress on the problem. It was just the nagging issue of nailing down a proof.

A proof that P = NP would have resulted in a lot of cryptographers committing Seppuku. The contrary proof doesn't have many huge implications, though.

Re:What would the impacts of this be for cryptogra (2, Insightful)

z-j-y (1056250) | more than 4 years ago | (#33183916)

It means we can breathe easy that a lot of crypto out there is now provably secure.

Wrong. It doesn't prove that there is no faster factoring algorithm.

Re:What would the impacts of this be for cryptogra (1)

noidentity (188756) | more than 4 years ago | (#33183968)

Doesn't P != NP simply mean that there exist crypto algorithms that are secure, but not necessarily that a particular one is secure?

Re:What would the impacts of this be for cryptogra (2, Interesting)

Peach Rings (1782482) | more than 4 years ago | (#33184002)

A proof that P = NP would have resulted in a lot of cryptographers committing Seppuku.

If I were a cryptographer, I'd be positively itching for someone to break RSA. A 30 year old univerally-used secure cryptosystem means no job. :)

In a world where no crypto is really secure, everyone hires their own cryptographer to build a custom cryptosystem. Let's see Bletchley Park mathematicians try to cleverly crack gigabytes of junk encrypted data when the keys wouldn't fit in all the notebooks required to fill their entire building floor to ceiling.

Re:What would the impacts of this be for cryptogra (1, Insightful)

Anonymous Coward | more than 4 years ago | (#33183902)

Showing that P=NP or showing the opposite has none of the practical consequences for anything that are often touted. It matters not in practice if there is some polynomial time algorithm that solves a problem - what matters in practice is only how quickly you can actually solve the problem on a computer. Polynomial time does not mean fast, it does not mean slow. It does correlate weakly with "fast" for many problems of interest, but that is all it does - it does not tell you if an algorithm is fast or not. Even if P=NP there is still the possibility that all polynomial time algorithms that prove this are so slow as to be irrelevant, and even if NP does not equal P, there is still the possibility that there are fast non-polynomial algorithms that solve any problem humans care about in an acceptable time. Thus NP=P is a theoretical question only - and a very important one at that. The completely separate question of solving the interesting NP-complete problems quickly in practice is the problem that actually does have all the consequences that are routinely misattributed to the theoretical P=NP question.

Re:What would the impacts of this be for cryptogra (2, Informative)

Anonymous Coward | more than 4 years ago | (#33184132)

Large integer factorization has not been shown to exist in NP-Complete (it is doubtful it does), it is know to exist in both NP and co-NP, it could exist in P (but it is doubtful) we just don't know. RSA public key crypto depends on the difficulty of factoring very large numbers. Currently there is no known efficient mechanism for determining the factors of a very large number. If P != NP we don't get a whole lot more than we have at the moment because we don't know exactly what complexity class integer factorization lives in. If P == NP then we have a serious problem because that requires there to be an efficient integer factorization algorithm. It is interesting that if P != NP we could very well end up in a situation where there are problems that have no efficient solution (not in P) but are not in the class NP-Complete (the "hardest" of the problems in NP). Integer factorization could very likely fall within this area.

Re:What would the impacts of this be for cryptogra (0)

Anonymous Coward | more than 4 years ago | (#33184236)

Luckily, my cryptographic scheme based on large Busy Beaver numbers remains theoretically sound.

Well that was an overly complex solution (0)

Anonymous Coward | more than 4 years ago | (#33183774)

P != NP because it has an N there.
Well, wait, N could be 0 and P could still be zero, so in essence i made nothing from something.
Be right back, building a blackhole machine

They took our jobs! (-1, Offtopic)

Anonymous Coward | more than 4 years ago | (#33183778)

Bet he got here on an H1-B; let's get rid of him!

P.S. On an H1-B here myself; pissed off at all the hatred.

Re:They took our jobs! (0, Offtopic)

gd2shoe (747932) | more than 4 years ago | (#33184182)

Misplaced hatred. (yes, this is off topic)

H1-B is a good thing for the US, but is sometimes abused by firms who wish to pay very low salaries with no benefits (sometimes practically holding the employee hostage). This behavior is bad for both the visa holder, and for the job market as a whole (supply and demand get skewed).

I apologize for those who cannot follow simple logic. (We'll just need to keep working on them.) The Xenophobes can apologize for themselves.

Re:They took our jobs! (0)

Anonymous Coward | more than 4 years ago | (#33184210)

Don't you have hedges to trim? We don't do siesta" here in America you lazy sod. Now get back to work before I deport your ass.

Wait and see (0)

Anonymous Coward | more than 4 years ago | (#33183782)

It will be awhile before his proof is confirmed but I was hoping that P=NP

From the wikipedia discussion page (1)

Spyware23 (1260322) | more than 4 years ago | (#33183822)

"Deolalikar's result is that "P (does not equal) NP (intersect) co-NP for Infinite Time Turing Machines". This is a special context - infinite time Turing machines are not the same thing as standard Turing machines, but are a kind of hypercomputer. Dcoetzee 09:07, 8 August 2010 (UTC)"

From http://en.wikipedia.org/wiki/Talk:P_versus_NP_problem#Potential_Solution [wikipedia.org]

Re:From the wikipedia discussion page (1)

Zaphod The 42nd (1205578) | more than 4 years ago | (#33183880)

I guess I'm just way out of my depths here, but it seems to me that a proof of P != NP for infinite time Turing machines would still mean about the same things to complexity theory, and therefor would apply to true Turing Machines anyways.

Or am I way off?

Re:From the wikipedia discussion page (4, Informative)

1729 (581437) | more than 4 years ago | (#33183894)

"Deolalikar's result is that "P (does not equal) NP (intersect) co-NP for Infinite Time Turing Machines". This is a special context - infinite time Turing machines are not the same thing as standard Turing machines, but are a kind of hypercomputer. Dcoetzee 09:07, 8 August 2010 (UTC)"

From http://en.wikipedia.org/wiki/Talk:P_versus_NP_problem#Potential_Solution [wikipedia.org]

That was a different paper, published in 2005:

http://portal.acm.org/citation.cfm?id=1185240 [acm.org]

oh dear (1)

pdbaby (609052) | more than 4 years ago | (#33183832)

While I'll wait until it's gone through peer review, I'm sure this means that news outlets will pick this up and misreport it... it's good PR for HP's research group either way!

View from the future (4, Informative)

Citizen of Earth (569446) | more than 4 years ago | (#33183840)

Of course they're not equal. It is revealed in Futurama episode 2-07.

Makes my job easier... (1)

offrdbandit (1331649) | more than 4 years ago | (#33183848)

The next time someone at work asks me to do something my response will be "I can't. That's NP."

Re:Makes my job easier... (4, Informative)

Zaphod The 42nd (1205578) | more than 4 years ago | (#33183862)

You can still solve NP problems, just not in polynomial time. There ARE solutions to travelling salesman, just not fast ones...

Re:Makes my job easier... (4, Informative)

loufoque (1400831) | more than 4 years ago | (#33183980)

There are fast solutions to the TSP, they're just not fast in pathological cases.

Re:Makes my job easier... (0)

Anonymous Coward | more than 4 years ago | (#33184066)

There's a difference between a solution and an approximation.
There are no fast solutions to the TSP, if there were, then P would be = NP.

Re:Makes my job easier... (2, Funny)

Surt (22457) | more than 4 years ago | (#33184258)

You forgot 'and I'm lazy'. Because NP is just hard, not impossible.

P != NP ? (0)

Anonymous Coward | more than 4 years ago | (#33183890)

But I thought that was how transistors work!

Is my computer now broken because of this guy?

Drat. (1)

kylemonger (686302) | more than 4 years ago | (#33183922)

Another good sf story [antipope.org] ruined. I was kinda looking forward to the aftereffects of a "P = NP" proof... it's been a dull Sunday.

XKCD was right (5, Funny)

wdsci (1204512) | more than 4 years ago | (#33183950)

If this has appeared somewhere in the other comments, sorry for missing it, but http://xkcd.com/664/ [xkcd.com] seems oh so appropriate here. (especially the alt text)

Re:XKCD was right (1)

John Hasler (414242) | more than 4 years ago | (#33184062)

Of ocurse he left out the part where it is the department head's name that goes on all those papers while the student is informed that this is not suitable material for his thesis...

Is there a link to the actual preprint / paper? (0)

Anonymous Coward | more than 4 years ago | (#33183996)

I don't know what kind of system scribd is trying to be, but it doesn't work with my browser, and I suspect it isn't the original / most direct link to the paper's preprint / public form. Isn't there just a simple direct PS / PDF / DVI / whatever link so one doesn't have to deal with scribd's brokenness (for me anyway)?

it's a constructive proof!!! (2, Funny)

PJ6 (1151747) | more than 4 years ago | (#33184024)

Yeah baby, we can now create an efficient way to break AES256 and decrypt the Wikileaks "insurance" file!

formal proof please (-1, Flamebait)

StripedCow (776465) | more than 4 years ago | (#33184038)

Can we please have a formal proof. A proof written in natural language and with a length of a hundred pages almost certainly contains some flaw. Just like a program of more than a few thousand lines of code is certain to contain at least one bug.

Re:formal proof please (0)

Anonymous Coward | more than 4 years ago | (#33184212)

Can we please have a formal proof. A proof written in natural language and with a length of a hundred pages almost certainly contains some flaw. Just like a program of more than a few thousand lines of code is certain to contain at least one bug.

But, extending that analogy, there's some problems you can't solve without a few thousand lines of code.

Re:formal proof please (4, Insightful)

iris-n (1276146) | more than 4 years ago | (#33184240)

Are you raving mad?

Of course there will be an error with this proof. Many errors, actually. Most of them irrelevant.
Maybe one of them is not. You know what? It will be caught in peer-review, exactly as it's been happening in the last centuries.

There's a reason noone uses formal proofs in mathematics. They're dull. They're slow. And we trust peer-review (for correctness, anyway).

What would be the use of a proof that no human can understand?

The new new HP way (0)

Anonymous Coward | more than 4 years ago | (#33184044)

So on about the same day CEO Mark Hurd collected a $53 million severance package from HP's board for either sexually harassing a contractor, or keeping said contractor as a mistress on an HP expense account, HP researcher Deolalikar submitted a paper which might earn him $1 million for proving one of the seven biggest unsolved problems in all of mathematics?

Pictures .... or it didn't happen (2, Interesting)

davidwr (791652) | more than 4 years ago | (#33184054)

Pictures, er, I mean, peer review, or it didn't happen.

Two questions (1)

slasho81 (455509) | more than 4 years ago | (#33184070)

Say this proof is correct, what are the implications and what is the next big problem?

Re:Two questions (1)

blitzkrieg3 (995849) | more than 4 years ago | (#33184172)

What is the next big problem?

You could try your hand at the other unsolved Millenium Prize Problems [wikipedia.org] .

Re:Two questions (1)

slasho81 (455509) | more than 4 years ago | (#33184184)

Sorry, I wasn't clear. I meant what's the next big problem in computer science.

There is a God! (1)

Sinan H (1548991) | more than 4 years ago | (#33184086)

I hope this brings closure to Computer Scientists. But you folks do realize that if P != NP then there is a God, If P = NP then there isn't. In other words, you can't have infinite "free efficiency". If you can do an infinitely complex task in reasonably efficient time then you can hack reality and get to God. God made P != NP so that we're locked in our own universe.

Re:There is a God! (1)

siride (974284) | more than 4 years ago | (#33184178)

Short answer: no. P == NP is about efficiency, not possibility. There, however, are algorithms, or problems to be solved, that are provably impossible to solve with computer (read: Turing machines).

paper is close but wrong (0)

Anonymous Coward | more than 4 years ago | (#33184090)

random k-SAT ensembles chosen have a flaw related to k,a factor graph ensemble. the paper is based on a statistical physics model which may also have probs but im unfamiliar with stat phy theory. -37028

Pulls up chair (1)

Schnoogs (1087081) | more than 4 years ago | (#33184110)

looking forward to reading the "let's pretend that I know something about computer science" posts from the monday morning scientists.

Re:Pulls up chair (0)

Anonymous Coward | more than 4 years ago | (#33184242)

Well, uh.... uh... duh... uh... That's what she said...

Isn't it... (0)

Anonymous Coward | more than 4 years ago | (#33184116)

I thought it was:

P / [ N^(-x) * N^(x)] = P

Tim R.

Not in arXiv? (5, Interesting)

iris-n (1276146) | more than 4 years ago | (#33184154)

I think this is the first time a serious researcher publishes a paper through email. Makes me wonder if he is actually publishing it or just asking for peer-review from his colleagues.

Or maybe he is trying to best Perelman in insanity. After all, even Perelman put the paper in arXiv.

Anyway, about the paper itself; I am a physicist, and he does say correct things about the Ising model and phase transitions. Unfortunately, it is only a small part of his proof that I can grasp. So I think he is dead serious.

Also, nice typography.

P= NP (1)

Surt (22457) | more than 4 years ago | (#33184180)

The 'proof' says so right on page 1.

Proof by example? (2, Interesting)

Anonymous Coward | more than 4 years ago | (#33184188)

I recall reading that Minesweeper was an NP complete, or at least NP Hard problem. Doesn't P mean that a solution is computable is a reasonable time? If that's the case, then P!=NP by minesweeper.

Imagine you're almost done with a game of Minesweeper. 5 mines left. Your grid looks like this:

+----
| * * 2
| * * 3
| * * 2
| 2 2 1

Now, obviously each of the blocks on the outside, four of them, are mines. Which leaves two that you have no information about and can't _GET_ any information about. Which of the remaining two blocks is a mine?...

Would this be an example of P != NP, assuming Minesweeper is NP?

A real achievement... (4, Funny)

adamofgreyskull (640712) | more than 4 years ago | (#33184206)

At the time of writing, there are two comments on Greg Baker's blog, congratulating Vinay on making it onto Slashdot. Jeez...he's potentially solved one of (if not) the most important open problem in computing, which could land him a million dollars in prize money...but yeah...well done on making it into that most esteemed of online publications, Slashdot.
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>