Counting solutions to binomial complete intersections

Mostrar todas las versiones(3)

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

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Cattani, E., Dickenstein, A.
Formato: Artículo publishedVersion
Lenguaje:Inglés
Publicado: 2007
Materias:
# P-complete
Binomial ideal
Complete intersection
Computational methods
Polynomials
Problem solving
Vectors
Binomials
Polynomial time
Algebra
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_0885064X_v23_n1_p82_Cattani
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paperaa:paper_0885064X_v23_n1_p82_Cattani
record_format dspace
spelling paperaa:paper_0885064X_v23_n1_p82_Cattani2023-06-12T16:48:19Z Counting solutions to binomial complete intersections J. Complexity 2007;23(1):82-107 Cattani, E. Dickenstein, A. # P-complete Binomial ideal Complete intersection Computational methods Polynomials Problem solving Vectors Binomials Complete intersection Polynomial time Algebra 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. Fil:Cattani, E. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Dickenstein, A. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2007 info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion application/pdf eng info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_0885064X_v23_n1_p82_Cattani
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language Inglés
orig_language_str_mv eng
topic # P-complete
Binomial ideal
Complete intersection
Computational methods
Polynomials
Problem solving
Vectors
Binomials
Complete intersection
Polynomial time
Algebra
spellingShingle # P-complete
Binomial ideal
Complete intersection
Computational methods
Polynomials
Problem solving
Vectors
Binomials
Complete intersection
Polynomial time
Algebra
Cattani, E.
Dickenstein, A.
Counting solutions to binomial complete intersections
topic_facet # P-complete
Binomial ideal
Complete intersection
Computational methods
Polynomials
Problem solving
Vectors
Binomials
Complete intersection
Polynomial time
Algebra
description 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.
format Artículo
Artículo
publishedVersion
author Cattani, E.
Dickenstein, A.
author_facet Cattani, E.
Dickenstein, A.
author_sort Cattani, E.
title Counting solutions to binomial complete intersections
title_short Counting solutions to binomial complete intersections
title_full Counting solutions to binomial complete intersections
title_fullStr Counting solutions to binomial complete intersections
title_full_unstemmed Counting solutions to binomial complete intersections
title_sort counting solutions to binomial complete intersections
publishDate 2007
url http://hdl.handle.net/20.500.12110/paper_0885064X_v23_n1_p82_Cattani
work_keys_str_mv AT cattanie countingsolutionstobinomialcompleteintersections
AT dickensteina countingsolutionstobinomialcompleteintersections
_version_ 1769810123793891328

Ejemplares similares