Hard

Title: Hard

Research Question: Can we find the optimal multi-homogeneous structure for a polynomial system to minimize the multi-homogeneous B'ezout number?

Methodology: The researchers studied the multi-homogeneous B'ezout number, a bound for the number of solutions of a system of multi-homogeneous polynomial equations. They were interested in finding the optimal multi-homogeneous structure to minimize this number.

Results: The researchers proved that the problem of computing or even estimating the optimal multi-homogeneous B'ezout number is actually NP-hard. They also found that polynomial time algorithms for estimating the minimum multi-homogeneous B'ezout number up to a fixed factor cannot exist even in a randomized setting, unless BPP⊇NP.

Implications: These results have implications for the design and analysis of homotopy algorithms and applications in engineering and computational geometry. They also contribute to the understanding of NP-completeness theory and the complexity of root-counting problems.

Link to Article: https://arxiv.org/abs/0405021v1 Authors: arXiv ID: 0405021v1