Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Intrinsic complexity estimates in polynomial optimization

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.\spar \noindent 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.\spar \noindent We design non-uniformly deterministic or uniformly probabilistic algorithms of intrinsic, quasi-polynomial complexity which solve these problems.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas
Contributor : Mohab Safey El Din <>
Submitted on : Thursday, April 18, 2013 - 11:14:48 AM
Last modification on : Friday, January 8, 2021 - 5:42:02 PM
Long-term archiving on: : Friday, July 19, 2013 - 4:01:21 AM


Files produced by the author(s)


  • HAL Id : hal-00815123, version 1
  • ARXIV : 1304.5214


Bernd Bank, Marc Giusti, Joos Heintz, Mohab Safey El Din. Intrinsic complexity estimates in polynomial optimization. 2013. ⟨hal-00815123v1⟩



Record views


Files downloads