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

[nietie.livejournal.com]

I'm not a scientist and I don't understand very much of it, but I can understand this is exciting news.

I sporfled at A US-based researcher has claimed to solve the sexiest problem in computer science. Sounds so much like Connor.

One of my dear friends, who passed away almost three years ago, worked at the Georgia Institute of Technology (that was mentioned in the article) for a few years. He was an expert in the field of mathematics and psychology.

[joereaves.livejournal.com]

*tilts head* Is this the thing Charlie Eppes covers whiteboards with whenever he doesn't want to think?

[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.

[joereaves.livejournal.com]

http://www.bbc.co.uk/news/science-environment-10938302

This is the BBC article on it. Focusses more on saying it might not work than explaining what it is.

[fififolle]

My brain hurts, but I love stuff like this. It would be cool if his proof works. I suspect it won't, but hey, he tried.

Tetris is NP-hard

[ewx.livejournal.com]

And indeed NP-complete (http://arxiv.org/abs/cs.CC/0210020), apparently; the Slashdot article in the middle of the link chain back to the original seems to have weakened the claim for some reason.