[thelema314]

> Given any two cities, a and b out of N, we do not know which one is visited first in the shortest path, and we certainly don't know what a's successor will be in the solution. Even verifying a solution to the problem (Is this sequence of cities the shortest path?) cannot be done in polynomial time.

Usually, the problem is simplified to a threshold test, like: Does this tour have path length < X? These kind of problems are equivalently difficult to produce solutions for in the general case, but are straightforward to verify.

[kazinator]

That's true; "hard to verify" isn't the good criterion either for a succinct distinction; all kinds of hard problems are easy to verify in poly time, including a modified version of this one.

[thelema314]

The most succinct informal description I have for NP-complete problems is lack of optimal substructure; that is, given a solution to part of the problem, it's possible for that to not help at all for solving the whole problem.

For Traveling Salesman, this means that given the best tour for an N-city graph, the best tour for the same graph augmented by a single vertex could be entirely different.

[kazinator]

Yes, bingo.

And this is easy to then contrast with, say, sorting, to counter the earlier objection.

We can split the set into two, sort the two parts individually and then trivially merge the results. We cannot split the cities into two, solve the traveling salesman problem, and then easily merge the results.

And adding a new element to a sorted list is just a linear insertion.