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 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! *