A probabilistic algorithm to compute the real dimension of a semi-algebraic set

Mohab Safey El Din 1 Elias Tsigaridas 1
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : Let $\RR$ be a real closed field (e.g. the field of real numbers) and $\mathscr{S} \subset \RR^n$ be a semi-algebraic set defined as the set of points in $\RR^n$ satisfying a system of $s$ equalities and inequalities of multivariate polynomials in $n$ variables, of degree at most $D$, with coefficients in an ordered ring $\ZZ$ contained in $\RR$. We consider the problem of computing the {\em real dimension}, $d$, of $\mathscr{S}$. The real dimension is the first topological invariant of interest; it measures the number of degrees of freedom available to move in the set. Thus, computing the real dimension is one of the most important and fundamental problems in computational real algebraic geometry. The problem is ${\rm NP}_{\mathbb{R}}$-complete in the Blum-Shub-Smale model of computation. The current algorithms (probabilistic or deterministic) for computing the real dimension have complexity $(s \, D)^{O(d(n-d))}$, that becomes $(s \, D)^{O(n^2)}$ in the worst-case. The existence of a probabilistic or deterministic algorithm for computing the real dimension with single exponential complexity with a factor better than ${O(n^2)}$ in the exponent in the worst-case, is a longstanding open problem. We provide a positive answer to this problem by introducing a probabilistic algorithm for computing the real dimension of a semi-algebraic set with complexity $( s\, D)^{O(n)}$.
Type de document :
Pré-publication, Document de travail
Several typos fixed in Sections 4 and 5. There is an error in Section 5 and thus the complexity r.. 2013
Liste complète des métadonnées

Littérature citée [50 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00808708
Contributeur : Elias Tsigaridas <>
Soumis le : jeudi 19 septembre 2013 - 09:35:39
Dernière modification le : vendredi 25 mai 2018 - 12:02:06
Document(s) archivé(s) le : jeudi 6 avril 2017 - 20:58:39

Fichiers

rd-07.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00808708, version 2
  • ARXIV : 1304.1928

Collections

Citation

Mohab Safey El Din, Elias Tsigaridas. A probabilistic algorithm to compute the real dimension of a semi-algebraic set. Several typos fixed in Sections 4 and 5. There is an error in Section 5 and thus the complexity r.. 2013. 〈hal-00808708v2〉

Partager

Métriques

Consultations de la notice

286

Téléchargements de fichiers

120