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&#x27;s possible for that to not help at all for solving the whole problem.<p>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.