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