Counting solutions to binomial complete intersections
Copyright policy )Counting solutions to binomial complete intersections
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.
Several minor improvements. Final version to appear in the J. of Complexity
- University of Massachusetts System United States
- Universidid De Buenos Aires Argentina
- University of Massachusetts Amherst United States
- UNIVERSITY OF MASSACHUSETTS United States
- University of Buenos Aires Argentina
complete intersections, Statistics and Probability, FOS: Computer and information sciences, Control and Optimization, Binomials, Computational Complexity (cs.CC), Computational aspects in algebraic geometry, Commutative Algebra (math.AC), Polynomials, binomial ideals, # P-complete, Polynomial time, Computational methods, FOS: Mathematics, Mathematics - Combinatorics, binomial ideal, Complete intersection, complete intersection, Problem solving, Numerical Analysis, Algebra and Number Theory, Applied Mathematics, #P-complete, Vectors, Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases), Mathematics - Commutative Algebra, Computer Science - Computational Complexity, Algebra, zero dimensional schemes, Complete intersections, Binomial ideal, Combinatorics (math.CO), Algebraic Geometry
complete intersections, Statistics and Probability, FOS: Computer and information sciences, Control and Optimization, Binomials, Computational Complexity (cs.CC), Computational aspects in algebraic geometry, Commutative Algebra (math.AC), Polynomials, binomial ideals, # P-complete, Polynomial time, Computational methods, FOS: Mathematics, Mathematics - Combinatorics, binomial ideal, Complete intersection, complete intersection, Problem solving, Numerical Analysis, Algebra and Number Theory, Applied Mathematics, #P-complete, Vectors, Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases), Mathematics - Commutative Algebra, Computer Science - Computational Complexity, Algebra, zero dimensional schemes, Complete intersections, Binomial ideal, Combinatorics (math.CO), Algebraic Geometry
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).10 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!