[gabrielgoh]

A simple example of this that has been shown rigorously is compressed sensing. Finding the sparsest vector, subject to linear constraints Ax = b is NP hard for general matrices, but is solvable in polynomial time if A satisfies the RIP property (e.g. w.h.p if A is generated by randomly sampling gaussians for each entry). Quite surprising!

[mturmon]

Another example (that may be related to yours) is the general linear programming problem, that is, for vector x,

  max c^T x

  s.t. A x <= b  [component-wise]

If problem instances (A, b) are chosen at random, from a rotationally-symmetric distribution, Borgwardt and others showed that, with high probability, the number of steps of the solution method is bounded by a polynomial in the number of dimensions. But on the other hand, there are explicit constructions of (A, b) that cause an exponential number of solution steps.

The usual interpretation is that "most" problems are friendly to the standard linear programming approach, but a few are not.

[jjgreen]

Sadly, that not many A arising in practice have the RIP property.