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 |
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