6 MARTIJN BAARTSE AND KLAUS MEER by first partitioning the problem’s variables into groups and then applying B´ezout’s theorem to each group. In many cases like the eigenvalue problem mentioned above the resulting bound is much closer to the true number of zeros than it is the case for the B´ ezout number. However, the question then again is how diﬃcult it is to find an optimal grouping of the variables such that the resulting upper bound is minimal. Though we deal with solving numerically systems of polynomials over the complex numbers, the above question leads to a typical problem about a combi- natorial optimization problem and thus into the framework of classical complexity theory. This is due to the structure of multi-homogeneous B´ ezout numbers. More precisely, the optimal grouping mentioned above only depends on the support of the given system, i.e., the structure of monomials with non-zero coeﬃcients. It is not important how these coeﬃcients look like. As consequence, the problem changes to a purely combinatorial one. The question of how diﬃcult it is to compute the op- timal variable partitioning has been answered in [66] which gives a hardness result for the problem. It is therefore suﬃcient to focus on particular polynomial systems, namely systems F := (f1,...,fn) = 0 in which all fi have the same support. More precisely, consider n ∈ N, a finite A ⊂ Nn and a polynomial system f1(z) = ∑ α∈A f1αz1 α1 zα2 2 · · · znn α , . . . , fn(z) = ∑ α∈A fnαz1 α1 zα2 2 · · · znn,α where the fiα are non-zero complex coeﬃcients. Thus, all fi have the same sup- port A. A multi-homogeneous structure is a partition of {1,...,n} into k subsets (I1,...,Ik) , Ij ⊆ {1,...,n}. For each such partition we define the block of vari- ables related to Ij as Zj = {zi|i ∈ Ij} the corresponding degree of fi with respect to Zj is dj := max α∈A l∈Ij αl. It is the same for all polynomials fi because all have the same support. Definition 2.1. a) The multi-homogeneous B´ ezout number with respect to support A and partition (I1,...,Ik) is the coeﬃcient of k j=1 ζ|Ik| j in the formal polynomial (d1ζ1 + · · · + dkζk)n, which is B´ ez(A, I1,...,Ik) = n |I1| |I2| · · · |Ik| k j=1 d |Ij| j . Here, we assume the fi to be not yet homogeneous with respect to variable group Zj otherwise, replace dj’s exponent by |Ij| − 1. b) The minimal multi-homogeneous B´ ezout number for a system having support A is min I partition B´ ez(A, I). It is known that this minimal number bounds the number of isolated solutions in a suitable product of projective spaces and trivially is never worse than the B´ ezout number, see [64, 100] for a proof. Unfortunately, as it is the case with Bernstein’s bound computing such an optimal partition is a hard task. Even if one would be satisfied with only approximating the minimal multi-homogeneous B´ ezout number using an eﬃcient Turing algorithm this is not likely possible. More precisely, the following holds: Theorem 2.2 ([66]). a) Given a polynomial system F : Cn → Cn with support A there is no polynomial time Turing-algorithm that computes the minimal multi- homogeneous B´ ezout number for A unless P = NP.

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2013 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.