Artículo

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

Abstract:

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.

Registro:

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
Año:2007
Volumen:23
Número:1
Página de inicio:82
Página de fin:107
DOI: http://dx.doi.org/10.1016/j.jco.2006.04.004
Handle:http://hdl.handle.net/20.500.12110/paper_0885064X_v23_n1_p82_Cattani
Título revista:Journal of Complexity
Título revista abreviado:J. Complexity
ISSN:0885064X
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_0885064X_v23_n1_p82_Cattani.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0885064X_v23_n1_p82_Cattani

Referencias:

  • 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

Citas:

---------- APA ----------
Cattani, E. & Dickenstein, A. (2007) . Counting solutions to binomial complete intersections. Journal of Complexity, 23(1), 82-107.
http://dx.doi.org/10.1016/j.jco.2006.04.004
---------- CHICAGO ----------
Cattani, E., Dickenstein, A. "Counting solutions to binomial complete intersections" . Journal of Complexity 23, no. 1 (2007) : 82-107.
http://dx.doi.org/10.1016/j.jco.2006.04.004
---------- MLA ----------
Cattani, E., Dickenstein, A. "Counting solutions to binomial complete intersections" . Journal of Complexity, vol. 23, no. 1, 2007, pp. 82-107.
http://dx.doi.org/10.1016/j.jco.2006.04.004
---------- VANCOUVER ----------
Cattani, E., Dickenstein, A. Counting solutions to binomial complete intersections. J. Complexity. 2007;23(1):82-107.
http://dx.doi.org/10.1016/j.jco.2006.04.004