Skip to Main content Skip to Navigation

The Complexity of local dimensions for constructible sets

Abstract : 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.
Document type :
Complete list of metadata
Contributor : Colette Orange Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:08:21 AM
Last modification on : Saturday, September 11, 2021 - 3:19:18 AM


Files produced by the author(s)


  • HAL Id : hal-02101861, version 1



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⟩



Les métriques sont temporairement indisponibles