Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Institut für Mathematik

Preprint 2013-07

Intrinsic complexity estimates in polynomial optimization.


Bernd Bank, Marc Giusti, Joos Heintz, Mohab D´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.