If the coefficients are non-negative then you can always do it with at most two integer evaluations.
That is, $P$ and $Q$ are equal if and only if
- $P(1)=Q(1)$, and
- $P(P(1)+1)=Q(Q(1)+1)$.
Update. If we allow for negative coefficients then this won't work. However, if in addition we are told that all coefficients $c$ satisfy $|c| \leq b$, then I believe we can do it with one integer evaluation. Namely, choose $n$ satisfying $n \geq 2b+1$. Then I think $P$ and $Q$ are equal if and only if
- $P(n)=Q(n)$.
See my comments below for an explanation.
