Intrinsic complexity estimates in polynomial optimization

Bernd Bank , Marc Giusti , Joos Heintz , Mohab Safey El Din

Preprint series: Institut für Mathematik, Humboldt-Universität zu Berlin (ISSN 0863-0976), 13-07, 18 pages

MSC 2000

14P10 Semialgebraic sets and related spaces

68Q25 Analysis of algorithms and problem complexity

90C60 Abstract computational complexity for mathematical programming problems

68W30 Symbolic computation and algebraic computation

Abstract
It is known that point searching in basic semialgebraic sets and the search for globally minimal points in polynomial optimization tasks can be carried out using $(s\,d)^{O(n)}$ arithmetic operations, where $n$ and $s$ are the numbers of variables and constraints and $d$ is the maximal degree of the polynomials involved. We associate to each of these problems an intrinsic system degree which becomes in worst case of order $(n\,d)^{O(n)}$ and which measures the intrinsic complexity of the task under consideration. We design non-uniformly deterministic or uniformly probabilistic algorithms of intrinsic, quasi-polynomial complexity which solve these problems.