Mathematics – Number Theory
Scientific paper
1998-11-13
Mathematics
Number Theory
Scientific paper
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.
No associations
LandOfFree
On the Complexity of Diophantine Geometry in Low Dimensions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the Complexity of Diophantine Geometry in Low Dimensions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Complexity of Diophantine Geometry in Low Dimensions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-309732