A pretty good explaination of P / NP
So those of you who have been chatting with me recently know I’ve had my eye out for a layperson level introduction to what P/NP is. Why do I care? Well, this is something high school students have heard of and occasionally ask me about. I feel like the idea isn’t really THAT hard but almost every explanation I’ve looked at tends to require knowledge about things like nondeterminstic Turing machines.
So I ran across what seems like the best intro I’ve read thus far. It’s a little light on the exact details and tends to assume you understand what “polynomial time” is, but it does make things sound cool.
If you are aware of a better explanation, I’d love to hear it:
http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext