The Complexity of local dimensions for constructible sets - LARA - Libre accès aux rapports scientifiques et techniques Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 1999

The Complexity of local dimensions for constructible sets

Résumé

We show that deciding whether an algebraic variety has an irreducible component of codimension at least d is an \np_{\c}-complete problem for every fixed d (and is in the Arthur-Merlin class if we assume a bit model of computation). However, when d is not fixed but is instead part of the input, we show that the problem is not likely to be in \np_{\c} or in \conp_{\c}. These results are generalized to arbitrary constructible sets. We also study the complexity of a few other related problems. This report updates LIP report 98-10.
On montre que décider si une variété algébrique a une composante irréductible de codimension au moins d est un problème \np_{\c}-complet pour toute constante d (et est dans la classe Arthur-Merlin si on travaille avec un modèle de calcul booléen). Par contre, si d n'est pas fixé mais est au contraire un entier arbitraire donné en entrée, on montre que ce problème n'est probablement pas dans \np_{\c} ni dans \conp_{\c}. Ces résultats sont étendus aux ensembles constructibles. On étudie également la complexité de quelques problèmes connexes. Ce rapport est une mise à jour du rapport LIP 98-10.
Fichier principal
Vignette du fichier
RR1999-04.pdf (272.16 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

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

Identifiants

  • HAL Id : hal-02101861 , version 1

Citer

Pascal Koiran. The Complexity of local dimensions for constructible sets. [Research Report] LIP RR-1999-04, Laboratoire de l'informatique du parallélisme. 1999, 2+13p. ⟨hal-02101861⟩
9 Consultations
109 Téléchargements

Partager

Gmail Facebook X LinkedIn More