P quite possibly not equal to NP
Aug. 11th, 2010 10:20 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
purplecatThis 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.
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.
