Let $P\in \mathbb{R}\lbrack x\rbrack$ be given. (In practice, the coefficients could be given as, say, decimals to sufficient precision.) Let $M\geq 1$, and let $I$ be an interval in $\mathbb{R}/\mathbb{Z}$ of length $\epsilon \ll 1/M$. Can we find (more or less) quickly the values of $m$, $1\leq m\leq M$, such that that $P(m)\in I$?
Notes:
(a) For $P$ linear, this isn't hard. Let $P(x) = a_1 x + a_0$. By Dirichlet approximation (which we can implement quickly using continued fractions), there are $Q\sim M$, $q\leq Q$, $0\leq a<q$ such that $a_1 = a/q +\beta/q Q$, where $|\beta|\leq 1$. For $P(m) \in I$ to hold, we must have $m \equiv a^{-1} b \mod q$, where $b$ is of the form $(\lfloor (\alpha - a_0) q\rfloor + c) \mod q$, where $\alpha$ is the midpoint of $I$ (say) and $c=O(1)$. Let $0\leq r<q$ be such that $r\equiv q^{-1} b\mod q$. Then we are tasked with finding $k\leq L/q$ such that $P(k q + r) \in I$.
Now, $P(k q + r) \equiv \beta k/Q + a_1 r + a_0$, and so we must find $k\leq L/q\sim Q/q$ such that $\beta k/Q$ lies in an interval contained in $\lbrack 0,1/q\rbrack$. This we can do just by division (over $\mathbb{R}$).
(b) For $P$ of degree $\geq 2$, this cannot be very easy: for $q$ an integer, $L=q$, solving the special case $P(x) = x^2/q$ is equivalent to finding square roots mod $q$, and that is equivalent to factorizing $q$.
At the same time, I would see any algorithm that works in time $O_\epsilon(M^\epsilon)$ as being acceptable, so factorization isn't a hard barrier.