6 ms·

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

by nsnick 11y ago

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/no_the_tsp_isn_t_np_complete?lang=en https://www.ibm.com/developerworks/community/blogs/jfp/entry...

CJefferson 11y ago
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
- nsnick 11y ago
  So yeah in the video, traveling salesman should not have been included in NP
- ColinWright 11y ago
  > 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.
Ar-Curunir 11y ago
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.
hebdo 11y ago
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.
- deleted 11y ago
  [deleted]
SilasX 11y ago
>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.

by nsnick 11y ago

CJefferson 11y ago

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

nsnick 11y ago
So yeah in the video, traveling salesman should not have been included in NP
ColinWright 11y ago
> 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.

Ar-Curunir 11y ago

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.

hebdo 11y ago

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.

deleted 11y ago
[deleted]

SilasX 11y ago

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