The complexity of irreducible components - LARA - Libre accès aux rapports scientifiques et techniques
Rapport (Rapport De Recherche) Année : 1998

The complexity of irreducible components

Résumé

We show that deciding whether an algebraic variety has an irreducible component of codimension at least d is an NP-complete problem for every fixed d in the Blum-Shub-Smale model of computation over the complex numbers (and is in the Arthur-Merlin class if we assume a bit model of computation). This is the first part of a paper which will eventually provide similar results for semi-algebraic sets.
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-complet pour toute constante d dans le modèle de calcul de Blum-Shub-Smale sur les nombres complexes (et est dans la classe Arthur-Merlin si on travaille avec un modèle de calcul booléen). Ce rapport est la première partie d'un article qui présentera aussi des résultats similaires sur les ensembles semi-algébriques.
Fichier principal
Vignette du fichier
RR1998-10.pdf (141.88 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

  • HAL Id : hal-02101815 , version 1

Citer

Pascal Koiran. The complexity of irreducible components. [Research Report] LIP RR-1998-10, Laboratoire de l'informatique du parallélisme. 1998, 2+5p. ⟨hal-02101815⟩
28 Consultations
78 Téléchargements

Partager

More