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

1. $P(1)=Q(1)$, and
2. $P(P(1)+1)=Q(Q(1)+1)$.

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

1. $P(1)=Q(1)$, and
2. $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

1. $P(n)=Q(n)$.

See my comments below for an explanation.

If the coefficients are non-negative then you can always do it with two integer evaluations.

That is, $P$ and $Q$ are equal if and only if

1. $P(1)=Q(1)$, and
2. $P(P(1)+1)=Q(Q(1)+1)$.

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

1. $P(1)=Q(1)$, and
2. $P(P(1)+1)=Q(Q(1)+1)$.