Intuitively, we feel that larger solution spaces should make a problem harder because there are more possible solutions to consider. And of course this is true if exhaustive search is the only algorithm.
But CS is full of problems where the smaller space is NP-hard and the larger one isn't. Integer linear programming is a prominent example.
To resolve the intuition, we can think of the larger space as an "unconstrained" problem where the solution space is somehow natural and nice for the problem. From this perspective, the smaller space looks like an added constraint. Adding constraints usually makes problems harder.
> Adding constraints usually makes problems harder.
Adding constraints can also make a problem easier. Which is why you've carefully worded your sentence in this manner :-)
You clearly know about those edge cases, but I felt it necessary to elaborate on this point: Additional constraints can make a problem easier OR harder, depending on the problem and the search space. Its very non-intuitive.
But CS is full of problems where the smaller space is NP-hard and the larger one isn't. Integer linear programming is a prominent example.
To resolve the intuition, we can think of the larger space as an "unconstrained" problem where the solution space is somehow natural and nice for the problem. From this perspective, the smaller space looks like an added constraint. Adding constraints usually makes problems harder.