|
|
|
|
|
|
by ctrl_freak
3861 days ago
|
|
|
TSP is NP-hard -- we don't know if it's in NP (that is, we don't even know if there's a polynomial time algorithm to verify whether a proposed solution is optimal). The decision problem of TSP is NP-complete: > The problem has been shown to be NP-hard (more precisely, it is complete for the complexity class FPNP; see function problem), and the decision problem version ("given the costs and a number x, decide whether there is a round-trip route cheaper than x") is NP-complete.
( https://en.wikipedia.org/wiki/Travelling_salesman_problem#Co... ) The author got this wrong in the article -- just because you can check that each house has been visited in polynomial time proves nothing. |
|
|