Great introduction for anyone (such as myself) who found themselves quickly lost in most of the other posted discussions. Not only do you get a general idea of the proof, you feel better equipped to look back over those higher-level discussions.
This was originally posted on an undergrad mailing list at Tech. It helped me understand the the P≠NP paper better, so I asked the author to make a page for it.
> For example, the problem of determining whether a graph has a Hamiltonian cycle is in NP; given a path in the graph, it is fast to verify whether or not it is a Hamiltonian cycle.
Submitter is a bit out of touch with reality if he thinks "Non-Mathematicians" will get that example. Nice read overall though.
People who are good at math, but not mathematicians, will get it. There is very little hope of explaining P and NP to people who feel nervous in the presence of math and don't want to hear what a "polynomial" is.
Speaking of math, do you think you could throw a few integrals into some post, or a sequel to "Technical Explanation of Technical Explanations"? I have a friend who's mildly interested in LW because I read it, but isn't willing to read enough to solidify an opinion without that s-shaped signal of competence.
If you read the entire section from the beginning, you'll notice that you don't really need to know what a Hamiltonian cycle is to understand the explanation. A made-up property would have worked equally well.
Actually the concept of Hamiltonian cycles is decidedly easier and less mathy than even basic algebra. At Kansas University the lowest level math class was called Topics, and one of the areas covered was graph theory, including Hamiltonian cycles. I don't recall anyone having problems with the concept, whereas the same group of kids would struggle to add fractions.
For P/NP examples, I find SAT the easiest to explain to people not in CS. It's just: there are some things that can be true or false, and some statements about them using and, or, and not. You want to find a set of T/F assignments that makes all those statements true. And it's intuitively obvious to people that it's much easier to check if an assignment is right than to find one.
Sure, any reasonably intelligent person can grasp what a Hamiltonian Cycle is, once you explain it to them. But this article starts talking about 'em before it's defined 'em, which is just bad pedagogy.
Sure, you don't have to know what it is to understand the rest of the article, but it's still a pretty valid criticism.
(I did three years of undergrad maths and I had to go look up what a Hamiltonian cycle is.)
