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$?
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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. 

