  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 in the complexity class PSPACE:
  (I) Given polynomials f_1,...,f_m in Z[x_1,...,x_n] defining a variety of
dimension <=0 in C^n, find all solutions in Z^n of f_1=...=f_m=0. (II) For a
given polynomial f in Z[v,x,y] defining an irreducible nonsingular non-ruled
surface in C^3, decide the sentence ``\exists v \forall x \exists y such that
f(v,x,y)=0?'' quantified over N. Better still, we show that the truth of the
Generalized Riemann Hypothesis implies that detecting roots in Q^n for the
polynomial systems in (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 crypto-systems.
