Aug. 11th, 2010

purplecat: Programming the Eniac Computer (computing)
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.
purplecat: Programming the Eniac Computer (computing)
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.

Profile

purplecat: Hand Drawn picture of a Toy Cat (Default)
purplecat

April 2019

S M T W T F S
 1 234 5 6
7 8 91011 12 13
14 15 16 17 18 19 20
21222324252627
282930    

Tags

Style Credit

Expand Cut Tags

No cut tags