On the complexity of diophantine geometry in low dimensions
J. Maurice Rojas · 2003
We consider the average-case complexity of some otherwise undecidable or open Diophantine problems. More precisely, we show that the following two problems can be solved within PSPACE: I. Given polynomials f/sub 1/,...,f/sub m//spl isin/Z[x/sub 1/,...,x/sub n/] defining a variety of dimension /spl les/0 in C/sup n/, find all solutions in Z/sup n/ of f/sub 1/=/spl middot//spl middot//spl middot/=f/sub m/=0. II. For a given polynomial f/spl isin/Z[v,x,y] defining an irreducible nonsingular non-ruled surface in C/sup 3/, decide the sentence /spl exist/v /spl forall/x /spl exist/y f(v, z, y)=/sup ?/0, quantified over N. Better still, we show that the truth of the Generalized Riemann Hypothesis (GRH) implies that detecting roots in Q/sup n/ for the polynomial systems in problem (I) can be done via a two-round Arthur-Merlin protocol, i.e., well within the second level of the polynomial hierarchy. (Problem (I) is, of course, undecidable without the dimension assumption.) The decidability of problem (II) was previously unknown. Along the way, we also prove new complexity and size bounds for solving polynomial systems over C and Z/pZ. A practical point of interest is that the aforementioned Diophantine problems should perhaps be avoided in the construction of cryptosystems.