Hmm, it's not an NP-complete problem, but hopefully it's still relevant to (4) and to a question I think is implicit in (2).

It's well-known that linear programming is in P, but in practice the simplex algorithm (which is exponential in the worst case) is usually the fastest method to solve LP problems, and it's virtually always competitive with the polynomial-time interior point methods. However, sampling uniformly from some space of problems is an unrealistic model, so average-case analysis isn't convincing. Spielman and Tang introduced the notion of "smoothed analysis" to remedy this, and showed that the simplex algorithm has polynomial smoothed time complexity. Glancing at Spielman's page, it looks like this has been applied to the knapsack problem, although the link to the paper is broken.

Re (1): What do you mean by "small?" :) I suspect that the heuristics would fail to help much if you took a random instance of, say, 3SAT with the right number of clauses and variables, and reduced this to an instance of TSP. But you'd get some polynomial-size blowup, so...

Re (3): It's correct that the existence of such an algorithm, on its own, would imply neither P = NP nor P != NP. But for "practical considerations" it might be hugely important, depending on what the constants were, and it would certainly spur investigation into whether there was a worst-case polynomial algorithm along the same lines.

By the way, Impagliazzo talks about some of these issues (although not all of them; the paper's 15 years old and predates Spielman-Tang, for instance) in perhaps the greatest survey paper ever written. I highly recommend it.

Hmm, it's not an NP-complete problem, but hopefully it's still relevant to (4) and to a question I think is implicit in (2).

It's well-known that linear programming is in P, but in practice the simplex algorithm (which is exponential in the worst case) is usually the fastest method to solve LP problems, and it's virtually always competitive with the polynomial-time interior point methods. However, sampling uniformly from some space of problems is an unrealistic model, so average-case analysis isn't convincing. Spielman and Tang introduced the notion of "smoothed analysis" to remedy this, and showed that the simplex algorithm has polynomial smoothed time complexity. Glancing at Spielman's page, it looks like this has been applied to the knapsack problem, although the link to the paper is broken.

Re (1): What do you mean by "small?" :) I suspect that the heuristics would fail to help much if you took a random instance of, say, 3SAT with the right number of clauses and variables, and reduced this to an instance of TSP. But you'd get some polynomial-size blowup, so...

Re (3): It's correct that the existence of such an algorithm, on its own, would imply neither P = NP nor P != NP. But for "practical considerations" it might be hugely important, depending on what the constants were, and it would certainly spur investigation into whether there was a worst-case polynomial algorithm along the same lines.

ETA: Actually, here's a construction for an NP-complete problem and an algorithm which unconditionally runs in average-case polynomial time. The problem is the union of a language in P and an NP-complete language (solvable in exp(n) time), such that the number of instances of size n of the first problem is something like exp(n^3), while the number of instances of the second problem is exp(n).

So the interesting thing about (3) is what the existence of an average-case polynomial algorithm for every problem in NP would tell us. And there the answer is still "nothing," but it's conceivable that we could prove P = NP under this assumption.

By the way, Impagliazzo talks about some of these issues (although not all of them; the paper's 15 years old and predates Spielman-Tang, for instance) in perhaps the greatest survey paper ever written. I highly recommend it.