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: