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