Clarification of the terms "brute force" and "guess"

In the answer to the question “What exactly is a negligible (and non-negligible) function?”

There is a part in the explanation that – as far as my knowledge goes – is conflicting:

But instead of brute force, the adversary can guess (a polynomial number of) random values and hope to chance upon the right one.

From what I understand, a “brute force attack” attempts to guess (to exhaustion)… or am I missing something here? Can someone please explain the distinction in this context?

• I'm thinking that it has to do with being polynomially bounded which means many keys are not valid in the first place. Of course, an adversary is not going to choose invalid keys. So you need some other method to define security - the notion of a brute force attack doesn't hold anymore. Think of brute force as infinitely dumb, just iterating through every possible (bit) value. Even a dictionary attack is not brute force. Commented Jul 13, 2014 at 14:00