  We show that the decidability of an amplification of Hilbert's Tenth Problem
in three variables implies the existence of uncomputably large integral points
on certain algebraic curves. We obtain this as a corollary of a new positive
complexity result: the Diophantine prefixes EAE and EEAE are generically
decidable. This means, taking the former prefix as an example, that we give a
precise geometric classification of those polynomials f in Z[v,x,y] for which
the question...
  ``Does there exists a v in N such that for all x in N, there exists a y in N
with f(v,x,y)=0?''
  ...may be undecidable, and we show that this set of polynomials is quite
small in a rigourous sense. (The decidability of EAE was previously an open
question.) The analogous result for the prefix EEAE is even stronger. We thus
obtain a connection between the decidability of certain Diophantine problems,
height bounds for points on curves, and the geometry of certain complex
surfaces and 3-folds.
