Typically, efficient algorithms have a polynomial runtime and an exponentially-large solution space. This means that the problem must be easy in two senses: first, the problem can be solved in a polynomial number of steps, and second, the solution space must be very structured because the runtime is only polylogarithmic in the number of possible solutions.
However, sometimes these two notions diverge, and a problem is easy only in the first sense. For instance, a common technique in approximation algorithms and parameterized complexity is (roughly) to prove that the solution space can actually be restricted to a much smaller size than the naive definition and then use brute-force to find the best answer in this restricted space. If we can a priori restrict ourselves to, say, n^3 possible answers, but we still need to check each one, then in some sense such problems are still "hard" in that there's no better algorithm than brute-force.
Conversely, if we have a problem with a doubly-exponential number of possible answers, but we can solve it in only exponential time, then I'd like to say that such a problem is "easy" ("structured" may be a better word) since runtime is only log of the solution space size.
Does anyone know of any papers that consider something like hardness based on the gap between an efficient algorithm and brute-force or hardness relative to the size of the solution space?