Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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 :
Reports (Research report)
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 : Wednesday, October 26, 2022 - 8:14:57 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⟩



Record views


Files downloads