TOPICS IN REAL AND COMPLEX NUMBER COMPLEXITY THEORY 7 b) The same holds with respect to the task of eﬃciently approximating the minimal multi-homogeneous B´ ezout number within an arbitrary constant factor of the minimum. Proof. As mentioned already above the task of computing the best variable partition is a purely discrete one because its definition only depends on the discrete structure of the support of the given system. The proof thus shows that an eﬃcient algorithm for any of the two mentioned tasks would result in an eﬃcient algorithm for the 3-colouring problem in graph theory. This problem is well known to be NP- complete in discrete complexity theory. Relating graph colouring with the problem at hand is done by assigning to a given graph G over vertex set V monomials that have the vertices of G as its variables and reflect the presence of edges and triangles in G. Doing this appropriately will result in a polynomial system whose minimal multi-homogeneous B´ ezout number equals C := (3n)! n!n!n! in case the graph has a 3-colouring and otherwise is at least 4 3 C. This gives claim a). For the non- approximability result one performs a similar construction which allows to blow up the factor 4 3 to an arbitrary constant. For this construction, a multiplicative structure of the multi-homogeneous B´ ezout numbers is exploited. ✷ In practice this means that one has to decide whether one would prefer a longer pre-computation for getting a better starting system either by using mixed volumes or by determining a suitable multi-homogeneous structure or abstains from such a pre-computation. Choosing a random starting system also in theory is an important alternative here. A more recent application of multi-homogeneous B´ ezout numbers can be found in [7]. Finally note that they also play some role outside the realm of polynomial equation solving. An example is given in [37], where the number of roots is used to bound geometrical quantities such as volume and curvature which is applied to the theory of Linear Programming. The discussion in this section intended to show the wide range of interesting questions arising from different areas related to polynomial system solving. In engineering, many tasks can be formalized using such systems. Solving them then leads to demanding problems in many different disciplines, ranging from algebraic geometry over numerical analysis to algorithm design and complexity theory. Being the focus of the present paper we concentrate on complexity theory. Above we have seen a question arising from polynomial system solving and being located in the framework of combinatorial opimization. This is a typical area of interest in classical discrete complexity theory, where also (non-)approximability results like the one given in Theorem 2.2 are studied, see [4,51,52,59]. However, taking into account domains like R and C over which the systems are to be solved nearby other questions arise: Can we design deterministic algorithms that decide whether a general such system has a solution at all in the respective domain? General here in particular means that we do not longer relate the number of variables and polynomials. If such decision algorithms exist what is the intrinsic complexity of this problem, i.e., can we give good lower and upper bounds on the running time of such algorithms? Is there a way to compare related problems with respect to their complexity? These are also typical questions in classical complexity theory when dealing with a class of problems. Since we are interested in real and/or complex number instances the Turing model seems at least not appropriate to deal

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.