P quite possibly not equal to NP

[purplecat]

This is, in fact, incredibly exciting news. But I am at a loss about how to explain simply and clearly what it means or why it is exciting in a blog. However my best shot is:

A problem is solvable in Polynomial time (that's P) if, as you make the problem bigger, it doesn't take too much more time to solve (for a technical definition of "too much").

A problem is solvable in Non-deterministic Polynomial time (that's NP) if as you make the problem bigger it doesn't take too much time to check whether a solution is correct. That is you can check the solution in polynomial time. However you do need to have a solution to check first.

No one really knows if P = NP, i.e. whether if you can check a solution in polynomial time then there is a procedure for generating that solution that is also polynomial time. Mostly people have suspected that P doesn't equal NP, and an awful lot of computer security is based on this assumption. It's been an open problem in computer science and mathematics for decades and, pretty much, has been the major open question for that whole time.

Anyway a proof that P != NP was unveiled on Friday though, as I say, it's yet to be checked.

Nature discusses the proof.

Tetris, incidentally, is NP-hard, as are many puzzles and solitaire games that humans find challenging yet fun.

This entry was originally posted at http://purplecat.dreamwidth.org/15812.html.

Comments

[lukadreaming.livejournal.com]

OK, don't test me on this later *g*. The Nature piece seems to have made a good job of explaining it to non-experts. But isn't the following par stating the bleeding obvious? *g*

For better or worse, the new proof seems to show that the NP problems cannot be solved as easily as those in the P category.

[purplecat]

Well, that depends, it's just a rephrasing, really of "does P equal NP?" but that is the whole crux of the issue, are the two categories really the same or are they genuinely different.