I've been thinking of this prior knowledge as "domain reduction", or even "dimensionality reduction". The more I know about the problem, the more of the space I can just remove from the search before I start. In high dimensional spaces, each dimension removed can be loosely/conceptually like an order of magnitude.

I like your phrase too, as there are classes of knowledge about a problem that don't necessarily reduce the domain, depending on how you look at it, but can still be exploited.