The Real Dimension Problem is NPR-complete. - Archive ouverte HAL Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1997

The Real Dimension Problem is NPR-complete.

(1)
1

Résumé

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.
Fichier principal
Vignette du fichier
RR1997-36.pdf (230.42 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02102032 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02102032 , version 1

Citer

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⟩
11 Consultations
100 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More