Thank you for this. I've been trying to figure out the "big picture" of this, and it is helpful to have someone explain it who understands the minute details.
The traveling salesman is the easiest to understand, let's say you want to visit 11 city's which route is the fastest? It's easy to find out how long a route takes just add 10 numbers (the travel times between each city). However, there are basically 11! (11 * 10 * 9 * 8 ...) paths to look at. Add a new city, and there are suddenly 11 times as many options and each of them take 10% longer to compute (you add 11 numbers for each path vs 10). Going from 1001 to 1002 city's gives 1001 times as many routs, but calculating each route only takes 0.1% longer to compute (add 1000 vs 1001 numbers).
The only real hope if you want the perfect solution is for there be some secret that let's you eliminate many options without checking them. The simple truth is you can skip some steps aka, if your looking for the fastest trip though every major city in the US, you can ignore any path that starts with a longer trip than a complete path. AKA if you now of a route that visits every city in 21,357 miles you and you take longer than that to visit 80% of the city's you can ignore all paths that start that way. But, what are the limits on those improvements? What is the fastest possible approach?
PS: There are many options that can give a reasonably good solution, EX: if a computer picks the best random path from 1 million possible paths then it's probably better than 99.99% of the options. You can then take the best random paths and try to improve them by trying simple manipulations (swapping city's etc).
1) Formally, P vs. NP is presented as a binary YES/NO question rather than a "what is the smallest number such that <something>"? Only after you grasp the Y/N format of the question are you shown the trick where you can convert any problem in FNP into NP by converting it into a binary Y/N question with the help of a binary search. If you are presented initially with the TSP as the canonical P/NP problem, it is unclear for a while how it fits into the formal presentation
2) (If my understanding on this point is incorrect, I will be glad if someone disabuses me of my misconception): Sometimes, P vs. NP is presented as "problems to which it is harder to find the solution than to verify a solution once it's given". TSP is not actually one of those problems: if someone hands you a possible solution, the process for verifying that it is indeed correct is equivalent to finding it in the first place.
2) You're right; TSP is NP Hard, not NP Complete.
But if you're talking about the YES/NO version, then it is defined (ala Wikipedia) like this: "given the [graph and] costs and a number x, decide whether there is a round-trip route cheaper than x". This problem is NP Complete; it's easy to see that verifying in this case just means summing the weights and seeing if they are below `x`.
However, the mental model is vary close to the generic solution because someone can hand you the 2nd best solution which looks nothing like the best solution and you still need to find it. Where if you are handed the best solution they may be a shortcut to proving it's the best.
PS: The Clique problem always seemed like the version where shortcuts seemed most obvious. But, understanding why they fail is a larger mental jump IMO than NP Hard TSP to NP Complete TSP.