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?