I agree with both your example ("making the search space much smaller") and your explanation ("makes a big difference"), we just differ on whether thus changing the resource requirements constitutes a change in kind, or one in degree.

Also, I took your "code would likely be more complex" as "be less human-understandable", as opposed to its actual Kolmogorov complexity, which afaik would be identical.