Generally in theoretical cryptography the adversary is a probabilistic Turing machine that can take K steps to break your encryption, where K is asymptotically bounded by a polynomial function of the length of the input it is trying to break.

You will see this called a 'PPT' in the literature, where PPT = Probabilistic Polynomial Time.

Very generally, if your string is N bits, a polynomial attack is one that can solve it in O(n^i) bits, where i is some fixed number. A non-polynomial time attacker would be something beyond that, like O(2^n).

Technically this treats O(n^2) and O(n^10000) as the same effort.

I think you can loosely interpret polynomial as "practical." Worse than polynomial typically means exponential, which makes the problem too big to be practical to solve. A polynomial-sized problem is considered practical to solve.