# Decision problem wrt Pairs of Polynomials with Integer Coefficients

Given two arbitrary polynomials $G(x)$ and $H(y)$, with integer coefficents, are there any circumstances in which it is possible to decide whether or not $G(x) = H(y)$ has solutions with $x, y \in \mathbb Z$?

-
I can do it if they're linear –  Anthony Quas Jan 22 '13 at 0:31
If only it were that simple! :) –  Jim White Jan 22 '13 at 0:43

Qiaochu's comment is not correct. There is an explicit bound for the height of integral points on elliptic curves (from Baker's method) and so the problem is decidable. Other equations $y^n = G(x)$ are also decidable the same way. See e.g., Lang's book "Elliptic curves: Diophantine Analysis" where he puts some explicit bounds "under duress, at the insistence of Michel Waldschmidt" :-). I don't know if the current results cover the general case of the question.