Re:Computing Performance on the Horizon
by dragontamer on Monday July 05, 2021 @08:47PM
(#27743238)
> 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.