Kronecker’s smart, little black boxes. (English) Zbl 0978.65043

DeVore, Ronald A. (ed.) et al., Foundations of computational mathematics. Conference, Oxford, GB, July 18-28, 1999. Cambridge: Cambridge University Press. Lond. Math. Soc. Lect. Note Ser. 284, 69-104 (2001).
Summary: This paper is devoted to the complexity analysis of certain uniformity properties owned by all known symbolic methods of parametric polynomial equation solving (geometric elimination). It is shown that any parametric elimination procedure which is parsimonious with respect to branchings and divisions must necessarily have a non-polynomial sequential time complexity, even if highly efficient data structures (as e.g. the arithmetic circuit encoding of polynomials) are used.
For the entire collection see [Zbl 0962.00005].


65H10 Numerical computation of solutions to systems of equations
12Y05 Computational aspects of field theory and polynomials (MSC2010)
30C15 Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral)
26C10 Real polynomials: location of zeros
65Y20 Complexity and performance of numerical algorithms