The complexity of local dimensions for constructible sets

We show that deciding whether ran algebraic variety has an irreducible comp onent of codimension at least tl is an NPC-complete problem for every fixed ii (and is in the Arthur-ML rlin class if we assume a bit model of computa tion). However, when d is not fixed but is instead part of the input, we sh ow that the problem is not likely to be in NPC or in coNP(C). These results are generalized to arbitrary constructible. We also study the complexity o f a few other related problems. (C) 2000 Academic Press.