×

The membership problem for unmixed polynomial ideals is solvable in single exponential time. (English) Zbl 0747.13018

Summary: Deciding membership for polynomial ideals represents a classical problem of computational commutative algebra which is exponential space hard. This means that the usual algorithms for the membership problem which are based on linear algebra techniques have doubly exponential sequential worst case complexity. We show that the membership problem has single exponential sequential and polynomial parallel complexity for unmixed ideals. More specific complexity results are given for the special cases of zero-dimensional and complete intersection ideals.

MSC:

13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Atiyah, M. F.; McDonald, I. G., Introduction to Commutative Algebra (1969), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0175.03601
[2] Berenstein, C. A.; Yger, A., Bounds for the degrees in the division problem (1988), University of Maryland, Manuscript · Zbl 0698.45005
[3] Berkowitz, S. J., On computing the determinant in small parallel time using a small number of processors, Inform. Process. Lett., 18, 147-150 (1984) · Zbl 0541.68019
[4] Brownawell, D., Bounds for the degree in the Nullstellensatz, Ann. of math., 126, 2, 577-591 (1987) · Zbl 0641.14001
[5] Buchberger, B., An algorithm for finding a basis for the residue class ring of a zero dimensional polynomial ideal, (Ph.D. Thesis (1965), University of Innsbruck), (in German) · Zbl 1158.01306
[6] Buchberger, B., Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems, Aequationes math., 4, 374-383 (1970) · Zbl 0212.06401
[7] Buchberger, B., Gröbner-Bases: An algorithmic method in polynomial ideal theory, (Bose, N. K., Multidimensional System Theory (1985), Reidel: Reidel Dordrecht), 184-232 · Zbl 0587.13009
[8] Caniglia, L., Complejidad de algoritmos en Geometría Computacional, (Ph.D. Thesis (1989), Universidad de Buenos Aires)
[9] Caniglia, L.; Galligo, A.; Heintz, J., Some new effectivity bounds in computational geometry, (Mora, T., Proceedings 6th International Conference. Proceedings 6th International Conference, Rome, 1988. Proceedings 6th International Conference. Proceedings 6th International Conference, Rome, 1988, Lecture Notes in Computer Science, 357 (1989), Springer: Springer Berlin), 131-151, AAECC-6 · Zbl 0685.68044
[10] Caniglia, L.; Galligo, A.; Heintz, J., Borne simple exponentielle pour les degrés dans le théorèmes des zéros sur un corps de caractéristique quelconque, C.R. Acad. Sci. Paris Sér. 1, 307, 255-258 (1988) · Zbl 0686.14001
[11] Chistov, A. L.; Grigor’ev, D. Yu., Subexponential time solving systems of algebraic equations, LOMI Preprints E-9-83, E-10-83 (1983), Leningrad · Zbl 0596.12021
[12] Dickenstein, A.; Sessa, C., An effective residual criterion for the membership problem in \(C[z_1\),...,\(z_n\)] (1988), Manuscript
[13] J.C. Frangère, P. Gianni, D. Lazard and T. Mora, Efficient computation of zero dimensional Gröbner bases by change of ardering, J. Symbolic Comput., to appear.; J.C. Frangère, P. Gianni, D. Lazard and T. Mora, Efficient computation of zero dimensional Gröbner bases by change of ardering, J. Symbolic Comput., to appear.
[14] N. Fitchas and A. Galligo, Nullstellensatz effectif et Conjecture de Serre (Théorème de Quillen-Suslin) pour le Calcul Formel, Math. Nachr., to appear.; N. Fitchas and A. Galligo, Nullstellensatz effectif et Conjecture de Serre (Théorème de Quillen-Suslin) pour le Calcul Formel, Math. Nachr., to appear. · Zbl 0729.14001
[15] Galligo, A., Algorithmes de construction de bases standards (1985), University of Nice, Preprint
[16] von zur Gathen, J., Parallel arithmetic computations. A survey, (Proceedings 13th Symposium MFCS 1986. Proceedings 13th Symposium MFCS 1986, Lecture Notes in Computer Science, 233 (1986), Springer: Springer Berlin), 93-112 · Zbl 0616.68037
[17] Gianni, P.; Mora, T., Algebraic solution of polynomial equations using Groebner Bases, (Huguet, L.; Poli, A., Proceedings 5th International Conference. Proceedings 5th International Conference, Menorca, 1987. Proceedings 5th International Conference. Proceedings 5th International Conference, Menorca, 1987, Lecture Notes in Computer Science, 356 (1989), Springer: Springer Berlin), 247-257, AAECC-5
[18] Giusti, M., Combinatorial dimension theory of algebraic varieties, J. Symbolic Comput., 6, 249-265 (1988) · Zbl 0697.14001
[19] Giusti, M., Complexity of standard bases in projective dimension zero, (Davenport, J., EUROCAL ’87. EUROCAL ’87, Leipzig. EUROCAL ’87. EUROCAL ’87, Leipzig, Lecture Notes in Computer Science, 378 (1989), Springer: Springer Berlin), 333-335 · Zbl 1209.13034
[20] Heintz, J., Kybernet. Sb., Novaja Ser. Vyp., 22, 113-158 (1985), (in Russian) · Zbl 0589.03010
[21] Kollár, J., Sharp effective Nullstellensatz, J. Amer. Math. Soc., 1, 963-975 (1988) · Zbl 0682.14001
[22] Kredel, H.; Weispfenning, V., Computing dimension and independent sets of polynomial ideals, J. Symbolic Comput., 6, 231-247 (1988) · Zbl 0665.68024
[23] Lazard, D., Algèbre linéaire sur \(K[X_l\),...,\(X_n\)] etélimination, Bull. Soc. Math. France, 105, 165-190 (1977) · Zbl 0447.13008
[24] Lazard, D., Résolution des systèmes d’équations algébriques, Theoret. Comput. Sci., 15, 77-110 (1981) · Zbl 0459.68013
[25] Lejeune-Jalabert, M., Effectivitéde Calculs Polynomiaux, (Cours de D.E.A. (1985), Institut Fourier, Universitéde Grenoble I)
[26] Logar, A., A computational proof of the Noether’s Normalization Lemma, (Mora, T., Proceedings 6th International Conference. Proceedings 6th International Conference, Rome, 1988. Proceedings 6th International Conference. Proceedings 6th International Conference, Rome, 1988, Lecture Notes in Computer Science, 357 (1989), Springer: Springer Berlin), 259-273, AAECC-6 · Zbl 0673.13001
[27] Mayr, E.; Meyer, A., The complexity of the word problem for commutative semigroups and polynomial ideals, Adv. in Math., 46, 305-329 (1982) · Zbl 0506.03007
[28] Mulmuley, K., A fast parallel algorithm to compute the rank of a matrix over an arbitrary field, Proceedings 18th Annual ACM Symposium Theory of Computing, 338-339 (1986)
[29] Philippon, P., Théorème des zéros effectif d’après J. Kollár, Séminaire I.H.P. (1988)
[30] Shafarevich, I. R., Algebraic Geometry (1974), Springer: Springer Berlin · Zbl 0284.14001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.