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.
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|
Loading...