News for hackers. Stuff that matters.
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...