Comment by ithinkso | Hacker News Reader

Comment by ithinkso | Hacker News Reader

I've always enjoyed reading articles about P vs. NP problem but this one missed the point I think. First of all author stated that Unfortunately, many with computer science degrees have a weak understanding of the concept—let alone those without any training on it. but the explanation he gave is actually identical to those that are given in colleges and this is why people have weak understanding of NP problems.

He then lists three most common examples of NP problems that are not even as close to the real problems as he thinks they are.

This is why the P versus NP problem is so interesting to people. If anyone were to solve it, it would potentially make very difficult problems very easy. and here is where he missed the point completely. This is simply not true - if for example there is polynomial time algorithm solving NP problem then P vs. NP is solved but if this algorithm is lower bounded by, I don't know, n^(10^80) it's not so easy for computers either. It is 'useless' from real software point of view.

The most profound effect of proving that P=NP is that the ability to check any answer's correctness 'fast' (in polynomial time) is sufficient to being able to solve that problem in polynomial time. That's it. Pure theory of computation. No real life super computing boost.

> First of all author stated that Unfortunately, many with computer science degrees have a weak understanding of the concept—let alone those without any training on it. but the explanation he gave is actually identical to those that are given in colleges and this is why people have weak understanding of NP problems.

In a computer science class you should be going into the details. This was not designed to do that. It was designed to give a general overview of the concept, as is clearly stated in the beginning.

And I think the latter is more needed than the former. There are plenty of deep explanations of this topic, and very few approachable ones.

"very few approachable ones."

I give credit to the author for trying, but having "enjoyed" an automata theory class and having read the textbook there is no "royal road to P/NP" much like geometry. Have to take the entire long road to get to the end.

Analogy time... how would you explain recursion to a general populace without first explaining variables, functions, calling by ref vs value (or just the idea of calling a function at all, and that it returns something), stacks, the concept of procedural programming, the idea of a flowchart, some level of error detection so it doesn't run off into the weeds, some basic ideas about scalability... So Colbert invites you on his show and after the HN cheering dies down he says "I don't know much about computer science, could you explain recursion in plain language in a line or two?" Honestly, I'd probably say "No" or some joke about it being turtles all the way down which the general public wouldn't find very amusing but those who know would laugh.

There is no royal road; or if we want some mystical woo, we could say that the journey is the destination, or something. I think that if you're trying to understand P-vs-NP it's not a matter of proceeding definition by definition. It's more like simultaneously approaching the question from lots of different angles, in order to build the mental connections between P-vs-NP and other topics. That includes Turing machines, formal languages and automata, reductions, big-O analysis, important concrete problems in P, NP, or neither, important algorithms and methods, and so forth.

Recursion is probably the same way. For Colbert purposes you could certainly come up with some glib explanation. When I, or you, or anyone else, have learned recursion we've probably started with that, but then proceeded to build connections with induction, PL semantics, computer architecture, compiler/runtime implementations, and all the other allied topics.

But I do think the earliest, most informal, explanation has its place too, because you have to start somewhere. The learning process is (at least for me) more like proceeding through lots of explanations of the same thing, at greater levels of detail and with different metaphors and external references, than it is like a linear progression from topic to topic.

Reply on news.ycombinator.com