Just because a problem is NP-complete doesn't mean it can't be usually solved quickly.
The best example of this is probably the traveling salesman problem, for which extraordinarily large instances have been optimally solved using advanced heuristics, for instance sophisticated variations of branch-and-bound. The size of problems that can be solved exactly by these heuristics is mind-blowing, in comparison to the size one would naively predict from the fact that the problem is NP. For instance, a tour of all 25000 cities in Sweden has been solved, as has a VLSI of 85900 points (see here for info on both).
Now I have a few questions:
1) There special cases of reasonably small size where these heuristics either cannot find the optimal tour at all, or where they are extremely slow to do so?
2) In the average case (of uniformly distributed points, let's say), is it known whether the time to find the optimal tour using these heuristics is asymptotically exponential n, despite success in solving surprisingly large cases? Or is it asymptotically polynomial, or is such an analysis too difficult to perform?
3) Is it correct to say that the existence of an average-case polynomial, worst-case exponential time algorithm to solve NP problems has no importance for P=NP?
4) What can be said about the structure of problems that allow suprisingly large cases to be solved exactly through heuristic methods versus ones that don't?
Best Answer
This phenomenon extends beyond the traveling salesman problem, and even beyond NP, for there are even some undecidable problems with the feature that most instances can be solved very quickly.
There is an emerging subfield of complexity theory called generic-case complexity, which is concerned with decision problems in the generic case, the problem of solving most or nearly all instances of a given problem. This contrasts with the situtation in the classical complexity theory, where it is in effect the worst-case complexity that drives many complexity classifications. (And even for approximate solutions in NP-hard problems, the worst-case phenomenon is still present.)
Particularly interesting is the black-hole phenomenon, the phenomenon by which the difficulty of an infeasible or even undecidable problem is concentrated in a very tiny region, outside of which it is easy. (Here, tiny means tiny with respect to some natural measure, such as asymptotic density.) For example, many of the classical decision problems from combinatorial group theory, such as the word problem and the conjugacy problem are linear time solvable in the generic case. This phenomenon provides a negative answer to analogue of your question 1 for these problems. The fact that the problems are easily solved outside the black hole provides a negative answer to the analogue of question 2. And I think that the fact that these problems are actually undecidable as total problems suggests that this manner of solving almost all cases of a problem will not help us with P vs. NP, in your question 3.
For question 4, let me mention that an extreme version of the black-hole phenomenon is provided even by the classical halting problem. Of course, this is the most famous of undecidable problems. Nevertheless, Alexei Miasnikov and I proved that for one of the standard Turing machine models with a one-way infinite tape, there is an algorithm that solves the halting problem on a set of asymptotic measure one. That is, there is a set A of Turing machine programs, such that (1) almost every program is in A, in the sense of asymptotic density, (2) A is linear time decidable, and (3) the halting problem is linear time decidable for programs in A. This result appears in (J. D. Hamkins and A. Miasnikov, The halting problem is decidable on a set of asymptotic probability one, Notre Dame J. Formal Logic 47, 2006. http://arxiv.org/abs/math/0504351). Inside the black hole, the complement of A, of course, the problem is intractible. The proof, unfortunately, does not fully generalize to all the other implementations of Turing machines, since for other models one finds a black hole of some measure intermediate between 0 and 1, rather than measure 0.