Just another WordPress site
I’m sure this is as old as the internet, but it’s new to me. I’ve definitely seem something similar in my algo books (in the index for Loops says see Recursion, and for Recursion says see Loops.)
(via Reddit – What did the cooling system say to the sound card?)
This is from a few months back, but I figured that the N != NP problem is always relevant so I might as well post it.
Here’s a quick summary of the problem:
“P versus NP” is more than just an abstract mathematical puzzle. It seeks to determine–once and for all–which kinds of problems can be solved by computers, and which kinds cannot. “P”-class problems are “easy” for computers to solve; that is, solutions to these problems can be computed in a reasonable amount of time compared to the complexity of the problem. Meanwhile, for “NP” problems, a solution might be very hard to find–perhaps requiring billions of years’ worth of computation–but once found, it is easily checked.
The “P versus NP problem” asks whether these two classes are actually identical; that is, whether every NP problem is also a P problem. If P equals NP, every NP problem would contain a hidden shortcut, allowing computers to quickly find perfect solutions to them. But if P does not equal NP, then no such shortcuts exist, and computers’ problem-solving powers will remain fundamentally and permanently limited. Practical experience overwhelmingly suggests that P does not equal NP. But until someone provides a sound mathematical proof, the validity of the assumption remains open to question.
This past summer I worked for a social gaming company in Mountain View. I remember getting into a good discussion with some coworkers about this problem. That’s another reason why working in nerd-land was nice; conversations about unsolved computer science questions are par for the course. That being said, my algorithms class last semester was nearly the end of me.
What Does ‘P vs. NP’ Mean for the Rest of Us? -MIT Technology Review
(via Boing Boing)