Hacker News Reader

Comment by DanAndersen | Hacker News Reader

I definitely got a sense of mathematical awe out of that. Thanks for sharing.

I'm always impressed when I see someone who can communicate ideas, especially complex scientific concepts, clearly and effectively, using analogies in a proper way that doesn't just overwhelm the viewer (as a lot of popsci stuff does). It's a talent I know that I need to work on; as a fledgling academic attempting to write papers clearly I struggle with it. Does it simply come with practice or are there resources anyone here can recommend for improving one's ability to make hard ideas understandable?

View on HN

Sometimes these videos can over simplify to the point of not providing a complete understanding. For example I don't think he explains what a Non Deterministic Turing Machine is, or even mention the words Turing Machine. Also not mentioned is the fact that if a Non Deterministic Turing Machine can solve a problem in polynomial time, a Deterministic Turing Machine can solve the same problem in exponential time. So (correct me if I am wrong) a problem that can only be solved in factorial time on a Deterministic Turing Machine for example cannot be part of the class NP.

He also includes Traveling salesman in the class NP. I think there is some debate about whether traveling salesman is NP-Complete, as that would require a polynomial algorithm to check whether in fact your solution was the shortest. https://www.ibm.com/developerworks/community/blogs/jfp/entry...

There is no debate, plain travelling salesman is defiantly not known to be NP-complete. The usual solution for optimisation problems is to turn them into a decision problem, by saying "is there a path of length k or less?". Then it is in NP-complete

So yeah in the video, traveling salesman should not have been included in NP

  > There is no debate, plain travelling salesman
  > is defiantly not known to be NP-complete.

Actually, there is no debate, plain TSP is specifically not NP-complete and cannot be, because it's not a decision problem. So it's not just, as you say, "not known to be" but instead is "known not to be".

However, by using binary search you can convert a decision version of TSP into the optimisation version in polynomial time. In this sense it is perfectly reasonable to refer to TSP as being NP-Complete.

I agree completely that these sorts of differences actually matter when dealing with the technicalities, but in practice it makes sense not to worry too much when trying to explain the broader concepts.

To clarify your last point, P and NP are classes of 'decision' problems, i.e. problems for which we have a yes/no answer. TSP is commonly formulated as a combinatorial OPTIMIZATION problem

The decision version of TSP would be formulated as: Given a complete graph G and a budget b, decide if there exists a path that visits each node and has cumulative weight less than b.

If you have a solver for decision TSP, then you can solve the optimization version of TSP by performing binary search on the budget b.

I'm glossing over some details, but there's a clearer explanation on how to solve search problems with an oracle for decision problems in Sipser.

There is an alternative, equivalent definition of NP languages, through projections of certain polynomially bounded and P-verifiable relations. This is the strict mathematical base for the commonly spread and very valid observation, namely that for a decision problem to be in NP means for its solution to be verifiable in polynomial time.

Traveling salesman is in NP. There is no point debating this.

Edit: as others have pointed out: traveling salesman in in NP only when it is in its decision version. Otherwise the question does not make sense, as standard complexity classes are defined for decision problems, this is - for languages.

>He also includes Traveling salesman in the class NP. I think there is some debate about whether traveling salesman is NP-Complete, as that would require a polynomial algorithm to check whether in fact your solution was the shortest.

It's kind of imprecise, but the understanding in these situations is that you're talking about some bounded version of the problem. In TSP, it's common to mean the problem of "is there a solution of length less than N", and you're only verifying that the length is less than N, not that it's optimal.

As with writing in general, here's how I personally approach it:

1. Practice, practice, practice.

2. Find good examples (like this video) and try to extract and generalize the techniques that you think work really well.

and the last point which not everyone thinks of consciously:

3. Watch sports, read books, watch TV and movies, read the news, and go outside. When you must communicate by analogy, you need a broad pool of experiences to draw from so that you can match your audience.

Maybe this would be helpfull:

http://betterexplained.com/articles/adept-method/

It's by the author of better explained - a really great math teaching site.

Reply on news.ycombinator.com