purplecat: Hand Drawn picture of a Toy Cat (Default)
A lot of discussion has been going on on RJ Lipton's blog and he yesterday posted a summary of the progress in one week. On balance I'd say it doesn't look hopeful that Deolalikar's proof can be patched, but there's an interesting sociological process going on, especially for those of us with an interest in the nature of mathematical proof.

This entry was originally posted at http://purplecat.dreamwidth.org/15933.html.
purplecat: Hand Drawn picture of a Toy Cat (Default)
A lot of discussion has been going on on RJ Lipton's blog and he yesterday posted a summary of the progress in one week. On balance I'd say it doesn't look hopeful that Deolalikar's proof can be patched, but there's an interesting sociological process going on, especially for those of us with an interest in the nature of mathematical proof.
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.
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.

Profile

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

August 2017

S M T W T F S
   1 2 3 4 5
67 89101112
13 1415161718 19
20212223242526
2728293031  

Syndicate

RSS Atom

Tags

Style Credit

Expand Cut Tags

No cut tags