From: greg@math.ucdavis.edu (Greg Kuperberg)
Newsgroups: sci.math.research
Subject: Re: This week in the xxx mathematics archive (31 Aug - 4 Sep)
Date: 7 Sep 1998 13:27:13 -0700

In article <6sns97$5hl$1@manifold.math.ucdavis.edu>,
Greg Kuperberg <greg@math.ucdavis.edu> wrote:
>Rojas considers two simple variants of Hilbert's 10th problem.  The
>simpler one is decidability of Diophantine questions of the form "Is
>there an x such that for all y, there is a z such that P(x,y,z) = 0?"
>He relates this to problem of finding all integral points (or finding
>the largest integral point) on an algebraic curve.

I have learned by e-mail that this characterization of Maurice's paper
(http://front.math.ucdavis.edu/math.NT/9809009).  The correct statement
is that either a certain subproblem of EEAE is undecidable or finding
all integral points on an algebraic curve (Big-2) is nonrecursive.
(The paper discusses recursive upper bounds on the largest integral
point on an algebraic curve, but this is clearly equivalent to finding
all of them.)  "EEAE" is an abbreviation for:

    There exist x and y such that for all z, there exists w
    such that f(x,y,z,w)=0

where f is an integer polynomial.  This problem is known to be
undecidable, but Maurice considers a restricted class of f's where
the resulting problem EEAE' may or may not be undecidable.  EEAE'
is sufficiently simple that whether it or Big-2 is computationally
intractible, many number theory problems are hopeless in surprisingly
simple cases.
-- 
  /\  Greg Kuperberg (UC Davis)
 /  \
 \  / Visit the xxx Math Archive Front at http://front.math.ucdavis.edu/
  \/  * 5926+841 e-prints and counting! *