Artículo de Acceso Abierto. Puede ser descargado en su versión final
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor


We study the problem of counting the total number of affine solutions of a system of n binomials in n variables over an algebraically closed field of characteristic zero. We show that we may decide in polynomial time if that number is finite. We give a combinatorial formula for computing the total number of affine solutions (with or without multiplicity) from which we deduce that this counting problem is # P-complete. We discuss special cases in which this formula may be computed in polynomial time; in particular, this is true for generic exponent vectors. © 2006 Elsevier Inc. All rights reserved.


Documento: Artículo
Título:Counting solutions to binomial complete intersections
Autor:Cattani, E.; Dickenstein, A.
Filiación:Department of Mathematics and Statistics, University of Massachusetts, Amherst, MA 01003, United States
Departamento de Matematica, FCEyN, Universidad de Buenos Aires, 1428 Buenos Aires, Argentina
Palabras clave:# P-complete; Binomial ideal; Complete intersection; Computational methods; Polynomials; Problem solving; Vectors; Binomials; Complete intersection; Polynomial time; Algebra
Página de inicio:82
Página de fin:107
Título revista:Journal of Complexity
Título revista abreviado:J. Complexity


  • Barile, M., Morales, M., Thoma, A., On simplicial toric varieties which are set-theoretic complete intersections (2000) J. Algebra, 226 (2), pp. 880-892
  • Delorme, C., Sous-monoi{dotless}̈des d'intersection complète de N (1976) Ann. Sci. École Norm. Sup. (4), 91 (1), pp. 145-154
  • Dickenstein, A., Matusevich, L.F., Sadykov, T., Bivariate hypergeometric D-modules (2005) Adv. Math., 196 (1), pp. 78-123
  • Dickenstein, A., Sturmfels, B., Elimination theory in codimension two (2002) J. Symbolic Comput., 4, pp. 119-135
  • Duff, I.S., Reid, J.K., An implementation of Tarjan's algorithm for the block triangularization of a matrix (1978) ACM Trans. Math. Software, 4 (2), pp. 137-147
  • Eisenbud, D., Sturmfels, B., Binomial ideals (1996) Duke Math. J., 84 (1), pp. 1-45
  • Fischer, K.G., Morris, W., Shapiro, J., Affine semigroup rings that are complete intersections (1997) Proc. Amer. Math. Soc., 125 (11), pp. 3137-3145
  • Fischer, K.G., Morris, W., Shapiro, J., Mixed dominating matrices (1998) Linear Algebra Appl., 270, pp. 191-214
  • Fischer, K.G., Shapiro, J., Mixed matrices and binomial ideals (1996) J. Pure Appl. Algebra, 113 (1), pp. 39-54
  • Greuel, G.M., Pfister, G., (2002) A Singular Introduction to Commutative Algebra, , Springer, Berlin, Heidelberg, New York
  • Herzog, J., Generators and relations of abelian semigroups and semigroup rings (1970) Manuscripta Math., 3, pp. 175-193
  • Hoşten, S., Shapiro, J., Primary decomposition of lattice basis ideals (2000) J. Symbolic Comput., 29 (4-5), pp. 625-639
  • Kac, V.G., (1990) Infinite-Dimensional Lie Algebras. third ed., , Cambridge University Press, Cambridge
  • Koppenhagen, U., Mayr, E.W., An optimal algorithm for constructing the reduced Gröbner basis of binomial ideals (1999) J. Symbolic Comput., 28, pp. 317-338
  • Koppenhagen, U., Mayr, E.W., An optimal algorithm for constructing the reduced Gröbner basis of binomial ideals and applications to commutative semigroups (2001) J. Symbolic Comput., 31, pp. 259-276
  • Koppenhagen, U., Mayr, E.W., (1996) Computational Algebra and Number Theory, , Milwaukee, WI
  • Mayr, E.W., Meyer, A.R., The complexity of the word problem for commutative semigroups and polynomial ideals (1982) Adv. Math., 46 (3), pp. 305-329
  • Ponzoni, I., Sánchez, M.C., Brignole, N.B., Permutation of sparse matrices to a specific lower btf using graph decompositions (1998) Electron. J. Sociology, 1 (1), pp. 76-87
  • Provan, J.S., Ball, M.O., The complexity of counting cuts and of computing the probability that a graph is connected (1983) SIAM J. Comput., 12 (4), pp. 777-788
  • Saito, M., Sturmfels, B., Takayama, N., (2000) Gröbner deformations of hypergeometric differential equations, Algorithms and Computation in Mathematics, 6. , Springer, Berlin
  • Scheja, G., Scheja, O., Storch, U., On regular sequences of binomials (1999) Manuscripta Math., 98 (1), pp. 115-132
  • Steward, D.V., On an approach to techniques for the analysis of the structure of large systems of equations (1962) SIAM Rev., 4, pp. 321-342
  • Sturmfels, B., (1996) Gröbner bases and convex polytopes, University Lecture Series, 8. , American Mathematical Society, Providence, RI
  • Sturmfels, B., (2002) Solving Systems of Polynomial Equations, CBMS Regional Conference Series in Mathematics, 97. , AMS, Providence, RI
  • Tarjan, R., Depth-first search and linear graph algorithms (1972) SIAM J. Comput., 1 (2), pp. 146-160
  • Valiant, L.G., The complexity of enumeration and reliability problems (1979) SIAM J. Comput., 8, pp. 410-421


---------- APA ----------
Cattani, E. & Dickenstein, A. (2007) . Counting solutions to binomial complete intersections. Journal of Complexity, 23(1), 82-107.
---------- CHICAGO ----------
Cattani, E., Dickenstein, A. "Counting solutions to binomial complete intersections" . Journal of Complexity 23, no. 1 (2007) : 82-107.
---------- MLA ----------
Cattani, E., Dickenstein, A. "Counting solutions to binomial complete intersections" . Journal of Complexity, vol. 23, no. 1, 2007, pp. 82-107.
---------- VANCOUVER ----------
Cattani, E., Dickenstein, A. Counting solutions to binomial complete intersections. J. Complexity. 2007;23(1):82-107.