News for hackers. Stuff that matters.
Re:P ≠ NP by dalton on Sunday August 08, 2010 @03:25PM (#1585929)
WOW.

Assuming this isn't a hoax, and the proof holds up, this is front-page news kind of big deal.

As I recall, this has way more real-world practical usage than the Fermats Last Theorem proof.

Read the "Consequences of Proof" section in the Wikipedia article here: http://en.wikipedia.org/wiki/P_versus_NP_problem

[edit] The responses below are correct. Proving P=NP means the world gets turned upside down. P != NP is already sort of assumed.

Re:P ≠ NP by tzs on Sunday August 08, 2010 @04:03PM (#1586018)
It seems rather unlikely it would be a hoax. The author has published in this field before, in peer reviewed journals: http://logcom.oxfordjournals.org/cgi/content/abstract/15/5/5... or http://portal.acm.org/citation.cfm?id=1185240

Looking at his page at HP Research, he has several other publications in legitimate areas, and seems to be a well qualified researcher.

He may be wrong in this paper, but there's no reason to suspect its a hoax or that he's some kind of kook (as many other comments have sort of implied).

Re:P ≠ NP by ynniv on Sunday August 08, 2010 @03:37PM (#1585970)
a) Complicated academic proofs take (and should take) months if not years to verify, and will only be "front-page news" after verification. This is hardly the first unverified proof of the [edit: possible (in)]equality of P and NP.

b) The practical consequences of P=NP are immense. The practical consequences of P≠NP are that we can stop looking for computational unicorns and fairies.

We have for some time thought that P≠NP, but boy do people like those unicorns and fairies.

Re:P ≠ NP by Groxx on Sunday August 08, 2010 @05:33PM (#1586225)
I doubt it'll impact the unicorns-and-fairies searches significantly. Most people already work under the assumption that P≠NP.

Similarly, most people believe the world is round, and we go around the Sun. This hasn't prevented serious flat-Earthers nor geocentrists from existing.

Re:P ≠ NP by tel on Monday August 09, 2010 @09:44AM (#1587922)
It has been something of a damper on their funding, however.
Re:P ≠ NP by jacquesm on Sunday August 08, 2010 @04:35PM (#1586096)
> This is hardly the first unverified proof of the equality of P and NP.

in 'a' above didn't you mean to write 'inequality of P and NP' ?

Re:P ≠ NP by ynniv on Sunday August 08, 2010 @05:07PM (#1586161)
I meant the general field of equality as it relates to P an NP, but I have edited for clarity.
Re:P ≠ NP by macrael on Sunday August 08, 2010 @03:34PM (#1585962)
Well, assuming this proof holds up (and there are already links in the comments to other proofs that P != NP) they have proven what most people already assume, that the two are not equivalent. The consequences of P != NP are mostly just that people can stop spending time looking for ways for P to equal NP. Which is valuable, but doesn't have much "real-world practical usage"
[deleted]
Re:P ≠ NP by abstractbill on Sunday August 08, 2010 @03:41PM (#1585981)
A proof of P = NP would have huge practical consequences. A proof that P != NP "only" represents a huge advance in the theory of computation.
Re:P ≠ NP by carnevalem on Sunday August 08, 2010 @03:58PM (#1586007)
I hear this statement frequently when P = NP is discussed, but as someone not involved in computer science I have a hard time understanding it.

Could you explain what some of those consequences be? Does P = NP really need to be proved to achieve those practical consequences? Can't it just be assumed to be true and then see what the result is?

Re:P ≠ NP by abstractbill on Sunday August 08, 2010 @04:14PM (#1586048)
Intuitively:

NP questions take a long time to answer.

P questions take much less time.

The statement "P = NP" means that any NP question can be transformed into a P question. Answering the P question gives you an answer to the NP question.

So, if P = NP, then we can answer questions that we thought were slow, much more quickly than we would have thought possible.

Proving P = NP would (presumably) give you that method for transforming NP problems into P problems. So you would suddenly be able to figure things out easily that currently are hard and take a lot of computing power.

It's often assumed that P = NP would make cryptographic problems much easier to break, but apparently that's not really the case: http://world.std.com/~reinhold/p=np.txt

Re:P ≠ NP by miloshh on Sunday August 08, 2010 @04:39PM (#1586108)
Yeah, the common complaint against "P=NP would break cryptography" is "but what if the polynomial algorithm for (say) SAT is n^10000?". That is not very likely, in my opinion. Even though "polynomial" is not equivalent to "efficient", in practice all problems that have a polynomial algorithm also have an efficient algorithm.
Re:P ≠ NP by dfox on Sunday August 08, 2010 @08:59PM (#1586644)
There are many problems that have polynomial algorithm, that is not especially fast for practical problems (matrix multiplication comes to mind for example, for which there isn't even any proof that fastest known algorithm is in fact optimal)
Re:P ≠ NP by miloshh on Sunday August 08, 2010 @09:28PM (#1586696)
That's not a very good example - square matrix multiplication is O(n^1.5) (where n is the input size) and extremely fast in practice.

(Though, as you say, there could still be an O(n) algorithm - this is not known).

What I said is true even for linear programming (a P-complete problem) - it has polynomial and efficient algorithms - though the latter are actually not polynomial in the worst case. :)

Re:P ≠ NP by slug on Monday August 09, 2010 @03:59PM (#1589156)
Can you give a reference for a matrix multiplication algorithm which is O(n^1.5) ? thanks.
Re:P ≠ NP by miloshh on Monday August 09, 2010 @09:39PM (#1590154)
Note that I defined n as the input size...
Re:P ≠ NP by ramidarigaz on Sunday August 08, 2010 @04:10PM (#1586035)
If P = NP were proved to be true, it would tell us that there are solutions to a certain class of problems. Assuming it's true doesn't give us those solutions.

Wikipedia should answer most of your questions regarding the consequences:

http://en.wikipedia.org/wiki/P_%3D_NP#Consequences_of_proof

Re:P ≠ NP by nkassis on Sunday August 08, 2010 @05:16PM (#1586179)
To be a little more precise, proving P=NP would mean that there are algorithms to solve those problems that take polynomial time (can be calculated with a polynomial).

NP problems can be solved, it's just slow (think brute force method, running through all the possibilities).

Re:P ≠ NP by jules on Sunday August 08, 2010 @07:38PM (#1586499)
Not true. A polynomial time algorithm for NP complete programs is known (if P=NP that is). You just need to prove P=NP to prove that it is polynomial time.

http://en.wikipedia.org/wiki/P_versus_NP_problem#Polynomial-...

Re:P ≠ NP by lulin on Sunday August 08, 2010 @04:11PM (#1586036)
If I remember correctly, any proof of P = NP would be have to be constructive, so it would immediately give us a fast algorithm for ALL NP-complete problems, as they can all be reduced to each other.
Re:P ≠ NP by faboo on Sunday August 08, 2010 @09:53PM (#1586745)
It isn't actually _necessary_ for a P=NP proof to be constructive. A constructive proof would probably be easier to reason through, but it is prossible to prove the existence of an algorithm without providing one.
Re:P ≠ NP by btilly on Sunday August 08, 2010 @10:33PM (#1586828)
Not so. Pure existence proofs can be non-constructive.

The first historical example of an important proof which was non-constructive was Hilbert's Basis Theorem in 1888, which solved a famous problem posed by Paul Gordon. It is now viewed as in some sense being the first salvo in the debate over constructivism in the 20th century. See http://en.wikipedia.org/wiki/David_Hilbert#The_finiteness_th... for more.

Re:P ≠ NP by brg on Sunday August 08, 2010 @07:41PM (#1586504)
A proof that P != NP also represents the death of an era in which CS could look upon a single problem as motivation in hundreds of different directions.
Re:P ≠ NP by abstractbill on Sunday August 08, 2010 @07:56PM (#1586534)
True, but if the history of mathematics is a good guide CS will find other Big Problems in the future.
Re:P ≠ NP by kjrose on Sunday August 08, 2010 @03:42PM (#1585983)
Yeah, in general it's believed that any proof that P != NP would likely provide a lot of insight into which factors of an NP system make it difficult, and thus potentially allow us to divide even cleaner problems which are "easily" solved and problems which are "difficult to solve."
Re:P ≠ NP by gbhn on Sunday August 08, 2010 @03:42PM (#1585984)
The huge consequences are if P = NP (which no-one really believes).
Re:P ≠ NP by mjschultz on Sunday August 08, 2010 @03:33PM (#1585956)
Emphasizing the "assuming this isn't a hoax" part, even if it is correct, I don't think it is a life-changing deal.

Computer Scientists have been assuming for years that P does not equal NP, so they've been doing research with that assumption already in place. Proving that the assumption is correct won't hugely change anything.

I'm not trying to knock down the greatness of this proof, but the repercussions aren't going to be that major.

Re:P ≠ NP by miloshh on Sunday August 08, 2010 @04:13PM (#1586044)
I do not necessarily agree. There is a large number of open problems in computer science (especially in theory of complexity), and a correct proof of P != NP is very likely to use techniques that will help in resolving the other open problems. The techniques are also likely to change what we're learning in CS courses.