Hacker News Reader

Comment by patrickaljord | Hacker News Reader

> 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.

View on HN

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.

Or a Hamiltonian cycle...

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.

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.

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.)

Reply on news.ycombinator.com