The Real Dimension Problem is NPR-complete.

Pascal Koiran (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

We show that computing the dimension of a semi-algebraic set of R^n is an NP-complete problem in the Blum-Shub-Smale model of computation over the reals. Since this problem is easily seen to be NPR-hard, the main ingredient of the proof is an NPR algorithm for computing the dimension.

On montre que le calcul de la dimension d'un ensemble semi-algébrique de R^n est un problème NP-complet dans le modèle de Blum-Shub-Smale de calcul sur les nombres réels. Puisqu'il est facile de voir que ce problème est NPR-dur, le principal ingrédient de la preuve est un algorithme NPR de calcul de la dimension.

Mots clés: Blum-Shub-Smale Model; NP-Completeness; Semi-Algebraic Sets

Mots clés: Dimension; Ensembles Semi-Algébriques; Modèle de Blum-Shub-Smale; NP-Complétude

Domaines: Informatique [cs]

Pascal Koiran. The Real Dimension Problem is NPR-complete.. [Research Report] LIP RR-1997-36, Laboratoire de l'informatique du parallélisme. 1997, 2+12p. ⟨hal-02102032⟩