On the Complexity of Computing Multi-Homogeneous BÃƒÂ©zout Numbers

Meer, Klaus; Malajovich, Gregorio

doi:10.4230/DagSemProc.04401.9

Document

On the Complexity of Computing Multi-Homogeneous BÃƒÂ©zout Numbers

Authors Klaus Meer, Gregorio Malajovich

Part of: Volume: Dagstuhl Seminar Proceedings, Volume 4401
Part of: Series: Dagstuhl Seminar Proceedings (DagSemProc)
License: Creative Commons Attribution 4.0 International license
Publication Date: 2005-04-19

PDF

File

PDF

DagSemProc.04401.9.pdf

Filesize: 344 kB
16 pages

Document Identifiers

DOI: 10.4230/DagSemProc.04401.9
URN: urn:nbn:de:0030-drops-1460

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)

0

PDF Downloads

0

Metadata Views

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.

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

Author Details

Klaus Meer

Gregorio Malajovich

Any Issues?

Feedback on the Current Page

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail