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
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02101861
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:08:21 AM
Last modification on : Sunday, May 19, 2019 - 1:20:45 AM

File

RR1999-04.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101861, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

7

Files downloads

29