THE COMPLEXITY OF LOCAL DIMENSIONS FOR CONSTRUCTIBLE SETS

PASCAL KOIRAN

Abstract. We show that deciding whether an algebraic variety has an irreducible component of codimension at least d is an NP_{ℂ}-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_{ℂ} or in coNP_{ℂ}. These results are generalized to arbitrary constructible sets. We also study the complexity of a few other related problems.