Navegar

Colección

Datos Estadísticas

Artículo

Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

In this paper we obtain an effective algorithm for quantifier elimination over algebraically closed fields: For every effective infinite integral domain k, closed under the extraction of pth roots when the characteristic p of k is positive, and every prenex formula φ with r blocks of quantifiers involving s polynomials F1,...,Fs∈k[X1,...,Xn] encoded in dense form, there exists a well-parallelizable algorithm without divisions whose output is a quantifier-free formula equivalent to φ. The sequential complexity of this algorithm is bounded by O(|φ|) - D(O(n))r, where |φ| is the length of φ and D ≥ n is an upper bound for 1 + ∑si-1 deg Fi, and the polynomials in the output are encoded by means of a straight line program. The complexity bound obtained is better than the bounds of the known elimination algorithms, which are of the type |φ|.Dncr, where c ≥ 2 is a constant. This becomes notorious when r = 1 (i.e., when there is only one block of quantifiers): the complexity bounds known up to now are not less than Dn2, while our bound is DO(n). Moreover, in the particular case that there is only one block of existential quantifiers and the input polynomials are given by a straight line program, we construct an elimination algorithm with even better bounds which depend on the length of this straight line program: Given a formula of the type ∃xn-m + 1, . . . , ∃xn: F1(x1, . . . ,Xn) = 0 ∧ ⋯ ∧ Fs(x1, . . . ,Xn) = 0 ∧ G1(x1, . . . , Xn) ≠ 0 ∧ ⋯ ∧ Gs′ (x1, . . . ,xn) ≠ 0, where F1, . . . ,Fs ∈ k[X1, . . . ,Xn] are polynomials whose degrees in the m variables Xn-m+1,. . . ,Xn are bounded by an integer d ≥ m and G1, . . . ,Gs′ ∈ k[X1, . . . ,Xn] are polynomials whose degrees in the same variables are bounded by an integer δ, this algorithm eliminates quantifiers in time L2.(s.s′.δ)O(1).dO(m), where L is the length of the straight line program that encodes F1, . . . ,Fs, G1, . . . ,Gs′. Finally, we construct a fast algorithm to compute the Chow Form of an irreducible projective variety. The construction of all the algorithms mentioned above relies on a preprocessing whose cost exceedes the complexity classes considered (they are based on the construction of correct test sequences). In this sense, our algorithms are non-uniform but may be considered uniform as randomized algorithms (choosing the correct test sequences randomly). © 1998 Elsevier Science B.V. All rights reserved.

Registro:

Documento: Artículo
Título:An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs
Autor:Puddu, S.; Sabia, J.
Filiación:Departamento de Matemática, FCEyN - Univ. de Buenos Aires, Ciudad Universitaria, Pab. I, 1428 Buenos Aires, Argentina
Año:1998
Volumen:129
Número:2
Página de inicio:173
Página de fin:200
DOI: http://dx.doi.org/10.1016/S0022-4049(97)00068-6
Título revista:Journal of Pure and Applied Algebra
Título revista abreviado:J. Pure Appl. Algebra
ISSN:00224049
CODEN:JPAAA
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_00224049_v129_n2_p173_Puddu.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00224049_v129_n2_p173_Puddu

Referencias:

  • Amoroso, F., Tests d'appartenance d'après un théorème de kollár (1989) Acad. Sci. Paris, Serie I Math., 309, pp. 691-694
  • Balcázar, J.L., Díaz, J., Gabarró, J., Structural complexity I (1988) EATCS Monographs on Theoretical Computer Science, 11. , Springer, Berlin
  • Berenstein, C., Yger, A., Effective bezout identities in Q[X1, . . . ,Xn] (1991) Acta Math., 166, pp. 69-120
  • Berkowitz, S.J., On computing the determinant in small parallel time using a small number of processors (1984) Inform. Process. Lett., 18, pp. 147-150
  • Borodin, A., On relating time and space to size and depth (1977) SIAM J. Comput., 6, pp. 733-744
  • Borodin, A., Von Zur Gathen, J., Hopcroft, J., Fast parallel matrix and gcd computations (1982) Proc. 23rd Annual Symp. FOCS, pp. 65-71
  • Brownawell, D., Bounds for the degrees in the nullstellensatz (1987) Ann. Math. 2nd Series, 126 (3), pp. 577-591
  • Brownawell, D., (1989) A Prime Power Version of Nullstellensatz, , Manuscript
  • Caniglia, L., (1989) Complejidad de Algoritmos en Geometría Computacional, , Thesis, Universidad de Buenos Aires
  • Caniglia, L., How to compute the chow form of an unmixed polynomial ideal in single exponential time (1990) AAECC, , Springer, Berlin
  • Caniglia, L., Galligo, A., Heintz, J., Borne simple exponentielle pour les degrés dans le théorème des zéros sur un corps de caractéristique quelconque (1988) C.R. Acad. Sci. Paris T., 307, pp. 255-258. , Serie I
  • Caniglia, L., Galligo, A., Heintz, J., Some new effective bounds in computational geometry (1989) Lecture Notes in Computer Science, 357, pp. 131-151. , Proc. 6th Internat. Conf. Applied Algebra, Algebraic Algorithms and Error Correcting Codes, Rome 1988, Springer, Berlin
  • Caniglia, L., Guccione, J., Guccione, J.J., Local membership problems for polynomial ideals (1991) Progress in Mathematics, 94, pp. 31-45. , T. Mora, C. Traverso (Eds.), Proc. Internat. Conf. Effective Methods in Algebraic Geometry MEGA 90, Castiglioncello 1990, Birkhäuser, Basel
  • Chistov, A.L., Grigor'ev, D.Yu., (1983) Subexponential Time Solving Systems of Algebraic Equations I, II, , LOMI Preprints E-9-83, E-10-83, Leningrad
  • Chistov, A.L., Grigor'ev, D.Yu., Complexity of quantifier elimination in the theory of algebraically closed fields (1984) Lecture Notes in Computer Science, 176, pp. 17-31. , Proc. 11th Symp. MFCS 1984, Springer, Berlin
  • Fitchas, N., Galligo, A., Morgenstern, J., Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields (1990) J. Pure Appl. Algebra, 67, pp. 1-14
  • Fitchas, N., Giusti, M., Smietanski, F., Sur le complexité du théorème des zéros (1995) Approximation and Optimization in the Caribbean II, Proc. 2nd Internat. Conf. on Approximation and Optimization, pp. 274-329. , B. Brosowski, F. Deutsch, J. Gudatt (Eds.), La Habana, 1993, Peter Lang
  • Giusti, M., Heintz, J., La détermination des points isolés et de la dimension d'une variété algébrique peut se faire en temps polynomial (1993) Proc. Cortona Conf. on Computational Algebraic Geometry and Commutative Algebra, Symposia Matematica, 34. , D. Eiseinbud, L. Robbiano (Eds.), Istituto Nazionale di Alta Matematica, Cambridge University Press, Cambridge
  • Giusti, M., Heintz, J., Sabia, J., On the efficiency of effective nullstellensätze (1993) Comput. Complexity, 3, pp. 56-95
  • Giusti, M., Heintz, J., Morais, J.E., Morgenstern, J., Pardo, L.M., (1995) Straight Line Programs in Geometric Elimination Theory, , Manuscript
  • Grigor'ev, D.Yu., The complexity of the decision for the first order theory of algebraically closed fields (1987) Math. USRR Izvestija, 29 (2), pp. 459-475
  • Heintz, J., Definability and fast quantifier elimination over algebraically closed fields (1983) Theoret. Comput. Sci., 24, pp. 239-277
  • Heintz, J., On the computational complexity of polynomials and bilinear mappings, a survey (1989) Lecture Notes in Computer Science, 356, pp. 269-300. , L. Huguet, A. Poli (Eds.), Proc. 5th Internat. Conf. Applied Algebra, Algebraic Algorithms and Error Correcting Codes AAECC 5, Menorca, 1987, Springer, Berlin
  • Heintz, J., Schnorr, C.P., Testing polynomials which are easy to compute (1982) Monographie de L'enseignement Mathematique, 30, pp. 237-254. , Impr. Kundig, Geneve
  • Heintz, J., Sieveking, M., Absolute primality of polynomials is decidable in random polynomial time in the number of the variables (1981) Lecture Notes in Computer Science, 115. , 8th Internat. Colloquium on Automata, Languages and Programming ICALP 81, Springer, Berlin
  • Heintz, J., Wüthrich, R., An efficient quantifier elimination algorithm for algebraically closed fields (1975) SIGSAM Bull., 9, p. 11
  • Ierardi, D., Quantifier elimination in the theory of an algebraically-closed field (1989) J. ACM, pp. 138-147
  • Kaltofen, E., Greatest common divisors of polynomials given by straight line programs (1988) J. ACM, 35 (1), pp. 231-264
  • Kollar, J., Sharp effective nullstellensatz (1988) J. AMS, 1, pp. 963-975
  • Krick, T., (1990) Complejidad Para Problemas de Geometria Elemental, , Thesis, Universidad de Buenos Aires
  • Krick, T., Pardo, L.M., A computational method for diofantine approximation (1994) Proc. MEGA'94, Progress in Mathematics, , Birkhäuser, Basel
  • Matera, G., Turull, J.M., (1995) The Space Complexity of Elimination: Upper Bounds, , Manuscript
  • Mulmuley, K., A fast parallel algorithm to compute the rank of a matrix over an arbitrary field (1986) Proc. 18th ACM Symp. Theory of Computing, pp. 338-339
  • Nesterenko, Y.V., Estimates for the orders of zeros of functions of a certain class and applications in the theory of trascendental numbers (1977) Math. USSR Izvestija, 11 (2)
  • (1977) Izvestia Akad. Nauk. SSR Set-Mat. Tom, 41 (2)
  • Philippen, P., (1988) Théorème des Zéros Effectif D' Après J. Kollár, , Seminaire I.H.P
  • Renegar, J., On the computational complexity and geometry of the first-order theory of the reals (1992) J. Symbol. Comput., 13, pp. 253-352
  • Stoss, H.J., On the representation of rational functions of bounded complexity (1989) Theoret. Comput. Sci., 64, pp. 1-13
  • Strassen, V., Berechnung und programm I (1972) Acta Inform., 1, pp. 320-334
  • Tarski, A., (1951) A Decision Method for Elementary Algebra and Geometry, 2nd Ed., , Univ. of California Press, Berkeley, CA
  • Von Zur Gathen, J., Parallel arithmetic computations: A survey (1986) Lecture Notes in Computer Science, 233, pp. 93-112. , Proc. 13th Symp. MFCS 1986, Springer, Berlin
  • Wüthrich, R., (1977) Ein Quantoreneliminationverfahren für Die Theorie der Algebraisch Abgeschlossenen Körper, , Ph.D. Thesis, University of Zurich

Citas:

---------- APA ----------
Puddu, S. & Sabia, J. (1998) . An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs. Journal of Pure and Applied Algebra, 129(2), 173-200.
http://dx.doi.org/10.1016/S0022-4049(97)00068-6
---------- CHICAGO ----------
Puddu, S., Sabia, J. "An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs" . Journal of Pure and Applied Algebra 129, no. 2 (1998) : 173-200.
http://dx.doi.org/10.1016/S0022-4049(97)00068-6
---------- MLA ----------
Puddu, S., Sabia, J. "An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs" . Journal of Pure and Applied Algebra, vol. 129, no. 2, 1998, pp. 173-200.
http://dx.doi.org/10.1016/S0022-4049(97)00068-6
---------- VANCOUVER ----------
Puddu, S., Sabia, J. An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs. J. Pure Appl. Algebra. 1998;129(2):173-200.
http://dx.doi.org/10.1016/S0022-4049(97)00068-6