Log in

No account? Create an account
11 August 2010 @ 10:20 am
P quite possibly not equal to NP  
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.
Current Mood: excitedexcited
nietienietie on August 11th, 2010 10:16 am (UTC)
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.

louisedennis: primevallouisedennis on August 11th, 2010 12:22 pm (UTC)
I'm sure Connor would be very excited.
joereavesjoereaves on August 11th, 2010 12:02 pm (UTC)
*tilts head* Is this the thing Charlie Eppes covers whiteboards with whenever he doesn't want to think?
reggietate: labnickreggietate on August 11th, 2010 12:15 pm (UTC)
Maybe that's what Cutter's been doing with his curly matrix thingy. *g*(I'm writing Parallel Lines again, and it's muscled its way into the plot!)
louisedennis: primevallouisedennis on August 11th, 2010 12:22 pm (UTC)
For a moment there I thought you meant P=NP had made it's way into parallel lines!
louisedennis: mathematicslouisedennis on August 11th, 2010 12:21 pm (UTC)
I've only watched Numb3rs about twice but, if memory serves, yes it is.
fredbassettfredbassett on August 11th, 2010 12:33 pm (UTC)
Ah right, I was wondering that!
munchkinofdoommunchkinofdoom on August 11th, 2010 12:42 pm (UTC)
lukadreaminglukadreaming on August 11th, 2010 12:14 pm (UTC)
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.
louisedennis: mathematicslouisedennis on August 11th, 2010 12:24 pm (UTC)
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.
joereavesjoereaves on August 11th, 2010 03:21 pm (UTC)

This is the BBC article on it. Focusses more on saying it might not work than explaining what it is.
louisedennislouisedennis on August 16th, 2010 09:21 am (UTC)
The complexity theorists at work seem to be rather gloomy about it. Latest news is that some major flaws have been found in the paper. They don't necessarily kill the proof, but they do mean it isn't complete yet.
fififolle: Chuck Do What?fififolle on August 11th, 2010 03:40 pm (UTC)
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.
louisedennis: mathematicslouisedennis on August 16th, 2010 09:21 am (UTC)
At the moment it's not looking good for the proof, as it stands. Though it may be that it can be fixed.
fififolle: Primeval - Becker *whistle*fififolle on August 16th, 2010 08:06 pm (UTC)
How did I guess? :) I'm such a cynic.
ewxewx on August 11th, 2010 07:45 pm (UTC)
Tetris is NP-hard
And indeed NP-complete, apparently; the Slashdot article in the middle of the link chain back to the original seems to have weakened the claim for some reason.
louisedennis: mathematicslouisedennis on August 16th, 2010 09:22 am (UTC)
Re: Tetris is NP-hard
I would guess insufficient grasp of the terminology...