Hacker News Reader

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.

View on HN

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.

Reply on news.ycombinator.com