The complexity of irreducible components

Pascal Koiran (1)

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

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.

Mots clés: Blum-Shub-Smale Model; Irreducible Components; NP-completeness

Mots clés: Composantes Irréductibles; Dimension; Modèle de Blum-Shub-Smale; NP-complétude

Domaines: Informatique [cs]

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⟩