MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

3 added 382 characters in body; added 12 characters in body; deleted 14 characters in body

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.

2 added 8 characters in body

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)$.
1

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)$.