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

## 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 at 0:31 If only it were that simple! :) – Jim White Jan 22 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.