DagSemProc.04401.9.pdf
- Filesize: 344 kB
- 16 pages
Document
On the Complexity of Computing Multi-Homogeneous Bézout Numbers
Authors
-
Part of:
Volume:
Dagstuhl Seminar Proceedings, Volume 4401
Series: Dagstuhl Seminar Proceedings (DagSemProc) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2005-04-19
Cite As Get BibTex
Klaus Meer and Gregorio Malajovich. On the Complexity of Computing Multi-Homogeneous Bézout Numbers. In Algorithms and Complexity for Continuous Problems. Dagstuhl Seminar Proceedings, Volume 4401, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)
https://doi.org/10.4230/DagSemProc.04401.9
Abstract
We study the question how difficult it is to compute the multi-homogeneous B\'ezout number for a polynomial system of given number $n$ of variables and given support $A$ of monomials with non-zero coefficients. We show that this number is NP-hard to compute. It cannot even be efficiently approximated within an arbitrary, fixed factor unless P = NP. This is joint work with Gregorio Malajovich.
Subject Classification
Keywords
- multi-homogeneous Bézout numbers
- number of roots of polynomials
- approximation algorithms
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads