Computational Arithmetic Geometry I: Sentences Nearly in the Polynomial Hierarchy
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2000
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914099178242048 |
|---|---|
| author | Rojas, J. Maurice |
| author_facet | Rojas, J. Maurice |
| contents | We consider the average-case complexity of some otherwise undecidable or open Diophantine problems. More precisely, consider the following: (I) Given a polynomial f in Z[v,x,y], decide the sentence \exists v \forall x \exists y f(v,x,y)=0, with all three quantifiers ranging over N (or Z). (II) Given polynomials f_1,...,f_m in Z[x_1,...,x_n] with m>=n, decide if there is a rational solution to f_1=...=f_m=0. We show that, for almost all inputs, problem (I) can be done within coNP. The decidability of problem (I), over N and Z, was previously unknown. We also show that the Generalized Riemann Hypothesis (GRH) implies that, for almost all inputs, problem (II) can be done via within the complexity class PP^{NP^NP}, i.e., within the third level of the polynomial hierarchy. The decidability of problem (II), even in the case m=n=2, remains open in general.
Along the way, we prove results relating polynomial system solving over C, Q, and Z/pZ. We also prove a result on Galois groups associated to sparse polynomial systems which may be of independent interest. A practical observation is that the aforementioned Diophantine problems should perhaps be avoided in the construction of crypto-systems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_math_0005029 |
| institution | arXiv |
| publishDate | 2000 |
| record_format | arxiv |
| spellingShingle | Computational Arithmetic Geometry I: Sentences Nearly in the Polynomial Hierarchy Rojas, J. Maurice Number Theory Numerical Analysis Algebraic Geometry 11D72,11Y16,14G05,11G50,14M25,11R44 We consider the average-case complexity of some otherwise undecidable or open Diophantine problems. More precisely, consider the following: (I) Given a polynomial f in Z[v,x,y], decide the sentence \exists v \forall x \exists y f(v,x,y)=0, with all three quantifiers ranging over N (or Z). (II) Given polynomials f_1,...,f_m in Z[x_1,...,x_n] with m>=n, decide if there is a rational solution to f_1=...=f_m=0. We show that, for almost all inputs, problem (I) can be done within coNP. The decidability of problem (I), over N and Z, was previously unknown. We also show that the Generalized Riemann Hypothesis (GRH) implies that, for almost all inputs, problem (II) can be done via within the complexity class PP^{NP^NP}, i.e., within the third level of the polynomial hierarchy. The decidability of problem (II), even in the case m=n=2, remains open in general. Along the way, we prove results relating polynomial system solving over C, Q, and Z/pZ. We also prove a result on Galois groups associated to sparse polynomial systems which may be of independent interest. A practical observation is that the aforementioned Diophantine problems should perhaps be avoided in the construction of crypto-systems. |
| title | Computational Arithmetic Geometry I: Sentences Nearly in the Polynomial Hierarchy |
| topic | Number Theory Numerical Analysis Algebraic Geometry 11D72,11Y16,14G05,11G50,14M25,11R44 |
| url | https://arxiv.org/abs/math/0005029 |