A lot of complexity results are given with respect to bounded cases where results are more favourable.
For example, the graph isomorphism problem — which is GI-complete in general — is known to be tractable in cases where degree is bounded.
But every time I see such a result, I have a nagging voice in my head telling me that for any input graph the degree must be bounded. I find it hard to intuitively resolve the resulting cognitive dissonance.
I understand that bounding a parameter allows for considering it as a constant rather than a variable in the complexity analysis. But that seems almost like a semantic game since you can still define the bound to be arbitrarily large so long as it's fixed.
Perhaps the message to be gleaned from these bounded results is that if you assume the parameter in question to generally be small, the worst case is more favourable. But this seems rather vague to me since one can define "small" arbitrarily.
The nagging voice tells me I'm still missing something ... that something hasn't clicked.
To distil a question out of this: when one sees such a bounded-parameter result, what should one intuitively conclude about the problem in practice with respect to that parameter?
What is the importance of such a result?