Hacker News Reader

Comment by nsnick | Hacker News Reader

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

View on HN

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.

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

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

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

Reply on news.ycombinator.com