oc.optimization control - Hardness of combinatorial optimization after adding one constraint

Sure. We'll construct a normally trivial problem that turns into a question of four-coloring when we restrict one parameter.

For a graph $G$ on $n$ vertices, consider binary words of length $2n+1$. This will represent an assignment of colors 1-4 on the $n$ vertices, with the last bit telling us what the restriction on neighboring colors is. Namely, if the last digit is $i$, then $f$ spits out a 0 (calls it an improper coloring) if some pair of adjacent vertices have colors that are $i$ apart. When it is proper, $f$ spits out the reciprocal of the number of colors used.

Well, this is easy to maximize: just make every vertex the same color and choose the last digit to be 1. Congrats, you only used one color. But if our constraint is that the last digit is 0, then now you're asking whether the graph needs 1, 2, 3, 4, or more colors to properly color (in the usual sense), which you can't answer in polynomial time.