On the Complexity of Computing Multi-Homogeneous Bézout Numbers

Authors Klaus Meer, Gregorio Malajovich



PDF
Thumbnail PDF

File

DagSemProc.04401.9.pdf
  • Filesize: 344 kB
  • 16 pages

Document Identifiers

Author Details

Klaus Meer
Gregorio Malajovich

Cite AsGet 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.
Keywords
  • multi-homogeneous Bézout numbers
  • number of roots of polynomials
  • approximation algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail