The complexity of local dimensions for constructible sets
Pascal Koiran
We show that deciding whether an algebraic variety has an irreducible component of codimension at least d is an NP-complete problem over the field of complex numbers 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 or in co-NP over the complex numbers. These results are generalized to arbitrary constructible sets. We also study the complexity of a few other related problems.