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.

1. Introduction

It was shown in [14] that computing the dimension of algebraic varieties is NP_{ℂ}- complete in the Blum-Shub-Smale model of computation, and that in the bit model this problem is in AM (the Arthur-Merlin complexity class) assuming the Generalized Riemann Hypothesis (GRH). The dimension of a variety is the dimension of its largest irreducible component, and the dimensions of smaller components may also be of interest (see for instance [18]). In this paper we investigate the complexity of computing the dimensions of irreducible components, or more generally of computing local dimensions of constructible sets (given x_{0} ∈ ℂ^{n} and a constructible set X ⊆ ℂ^{n}, dim_{x_{0}}X is min dim(X ∩ O), where the minimum is taken over all Zariski open sets O containing x_{0}; if \overline{X} denotes the Zariski closure of X, this is also the largest dimension of an irreducible component of \overline{X} containing x_{0}). We consider both the classical model of computation and the Blum-Shub-Smale model. For previous work on the algorithmic aspects of the decomposition of a variety into its irreducible components, see [6, 7, 8] (the first two papers assume a bit model of computation), and [9] for the determination of isolated points.

The paper is organized as follows. In section 2 we recall some notions from classical and algebraic complexity theory. In section 3 we give algorithms for computing the Zariski closure of constructible sets and deciding whether a given point is isolated in a constructible set. Consider the following “codimension problem” CODIM_{ℂ}^{d}: given a variety V ⊆ ℂ^{n}, decide whether V has an an irreducible component of codimension at least d (i.e., of dimension ≤ n − d). In section 4 we show that this problem is NP_{ℂ}-complete for any fixed d. If V is defined by polynomial equations with integer coefficients given in bits, the corresponding CODIM^{d} problem is NP-hard, and belongs to AM (assuming GRH). In section 5 we show that if d is no longer fixed but is instead part of the input, the codimension problem is not likely to belong either to NP_{ℂ} or coNP_{ℂ}. Indeed, in both cases the classical polynomial-time hierarchy would collapse to its second level. Along the way, we show that it is coNP-hard to decide whether a variety has isolated points, and NP-hard to decide whether a system of homogeneous polynomial equations has a non-trivial solution. We also point out that NP_{ℂ} = coNP_{ℂ} would imply the collapse of the polynomial hierarchy to its second level. Section 5 ends with a few open problems. Finally, the results of section 4 are generalized to arbitrary constructible sets in section 6 (algebraic varieties are treated separately in section 4 because there is a simpler algorithm in that case).

2. Complexity of Computations

We recall that P_{ℂ} denotes the class of problems of ℂ^{∞} which can be solved in polynomial time in the Blum-Shub-Smale model of computation over the complex numbers [3]. Roughly speaking, a problem A ⊆ ℂ^{∞} is in P_{ℂ} if there is an algorithm which on any input x ∈ ℂ^{n} can decide whether x ∈ A in a number of arithmetic operations and equality tests which is polynomial in n. More background on this model of computation can be found in [2, 5, 17].

We also recall that A is in NP_{ℂ} if there exists a polynomial p(n) and a problem B ∈ P_{ℂ} such that for all x ∈ ℂ^{n}, x ∈ A if and only if there exists y ∈ ℂ^{p(n)} such that (x_{1}, …, x_{n}, y_{1}, …, y_{p(n)}) ∈ B. One can define the higher levels of the polynomial hierarchy over ℂ in a similar way (they will not be used in this paper).

As in the classical case, there are natural NP_{ℂ}-complete problems. Perhaps the simplest example is Hilbert’s Nullstellensatz (HN_{ℂ}): decide whether a system of polynomial equations in several complex variables has a solution. If we consider only polynomial equations with integer coefficients given in bits, the corresponding problem (call it HN) is known to be in the classical complexity class AM if we assume that the generalized Riemann hypothesis is true [12]. AM is a randomized version of NP which is located in the second level of the polynomial hierarchy (i.e., NP ⊆ AM ⊆ Π_{2}).

There is also a notion of randomization over ℂ: a problem A ⊆ ℂ^{∞} is said to be in BPP_{ℂ} if there exists a polynomial p(n) and a problem B ∈ P_{ℂ} such that for all x ∈ ℂ^{n}, x ∈ A if and only if the set of y ∈ ℂ^{p(n)} such that (x_{1}, …, x_{n}, y_{1}, …, y_{p(n)}) ∈ B is Zariski dense in ℂ^{p(n)}. However, the situation seems to be dramatically different from the classical case:

Proposition 1. BPP_{ℂ} = P_{ℂ}.

For a proof see [15], where a stronger result is established: generic quantifiers can be eliminated in polynomial time even in front of existential quantifiers (i.e., AM_{c} = NP_{ℂ} in the terminology of that paper; polynomial-time elimination is in fact possible in front of first-order formulas with a bounded number of quantifier alternations).

3. Isolated Points

We assume that a constructible set X ⊆ ℂ^{n} is given as a union of basic constructible sets X_{1}, …, X_{m}. Each X_{i} is described by a system of polynomial equalities of inequalities:

f_{i,1}(x) = 0, …, f_{i,s_{i}}(x) = 0; g_{i,1}(x) ≠ 0, …, g_{i,t_{i}}(x) ≠ 0. (1)

All polynomials are given in dense representation. In the sequel, D ≥ 3 is an upper bound on the degrees of the polynomials defining X.

We now give an algorithm (essentially due to Giusti and Heintz) for computing the Zariski closure of X. This algorithm describes \overline{X} as a union of intersections of zero sets of polynomials (there is one term in the union for each X_{i}).

Theorem 1. For every fixed integer n ≥ 0, the Zariski closure \overline{X} of X can be computed in polynomial time.

Proof. Since the closure of a union is the union of closures, we may assume that X is basic constructible. We therefore assume that X is described by a system of polynomial equalities and inequalities:

f_{1}(x) = 0, …, f_{s}(x) = 0; g(x) ≠ 0.

Note that if there are several inequalities g_{1}(x) ≠ 0, …, g_{t}(x) ≠ 0 in the system, they can be replaced by g(x) ≠ 0 where g is the product of the g_{i}’s.

Now we follow closely Giusti and Heintz ([8], Proposition 4.2.5), working out the bounds in greater detail. Let V = {x ∈ ℂ^{n}; f_{1}(x) = 0, …, f_{s}(x) = 0}, W = {x ∈ ℂ^{n}; g(x) = 0}, and let E′ be the finite-dimensional vector space of polynomials f ∈ ℂ[x_{1}, …, x_{n}] such that there exist polynomials p_{1}, …, p_{s} ∈ ℂ[x_{1}, …, x_{n}] satisfying deg(p_{i}f_{i}) ≤ D^{n}(D^{n} + 2D + 1) and

f · g^{D^{n}} = ∑_{i=1}^{s} p_{i}f_{i}. (2)

We claim that E′ defines the Zariski closure of X. This will yield the desired algorithm since we can compute a basis of E′ by linear algebra, and the polynomials of this basis will then define \overline{X}.

In order to prove the claim, we first show that \overline{X} ⊆ V (E′), where V (E′) is the algebraic set defined by E′. Since V (E′) is closed, it suffices to show that X ⊆ V (E′). Let x ∈ X and f ∈ E′. Since f_{1}(x) = ⋯ = f_{s}(x) = 0 and g(x) ≠ 0, it follows from (2) that f(x) = 0. Since this holds for an arbitrary f ∈ E′, we conclude that x ∈ V (E′).

Let us now establish the converse inclusion V (E′) ⊆ \overline{X}. By Proposition 3 from [11], \overline{X} can be defined by n + 1 polynomials f′_{1}, …, f′_{n+1} of degree bounded by deg(\overline{X}), and deg(\overline{X}) ≤ deg(V) ≤ D^{n} (the first inequality comes from the fact \overline{X} is a union of irreducible components of V, and the second from Bezout’s theorem). Since each f′_{j} vanishes on V − W, the product f′_{j}g vanishes on V, and by the effective Nullstellensatz [16] there exist polynomials p_{1}, …, p_{s} with deg(p_{i}f_{i}) ≤ D^{n}(D^{n} + D + 1) and an integer k ≤ D^{n} such that

(f′_{j}g)^{k} = ∑_{i=1}^{s} p_{i}f_{i}.

This can be rewritten as:

f′^{k}g^{D^{n}} = ∑_{i=1}^{s} g^{D^{n}−k}p_{i}f_{i},

and since deg(g^{D^{n}−k}p_{i}f_{i}) ≤ D^{n}(D^{n} + D + 1) + D^{n+1} we conclude that f′_{j}^{k} ∈ E′. Hence f′_{j} vanishes on V (E′). Since this holds for all j = 1, …, n + 1, we conclude that V (E′) ⊆ \overline{X}. This completes the proof of the claim, and of the theorem.

In the above proof, the coefficients of g = ∏_{1≤i≤t} g_{i} can be computed from the coefficients of the g_{i}’s by computing iteratively ∏_{2≤i≤j} g_{i} for j from 2 to t. This takes polynomial time since the number of variables is fixed (indeed, the number of monomials in g and in all intermediate products is bounded by \binom{Dt+n}{n}). The fact that products of polynomials in a constant number of variables can be computed efficiently is also used in the proofs of Theorem 2 and Theorem 9.

We say that a point x_{0} ∈ ℂ^{n} is isolated in X if there exists a Zariski open set O containing x_{0} such that (X − \{x_{0}\}) ∩ O = ∅, or equivalently if x_{0}∉\overline{X − \{x_{0}\}}. Note that if x_{0} is not isolated in X, this does not necessarily implies that x_{0} ∈ X. Of course, we say that X has an isolated point if there exists a point x_{0} ∈ X such that x_{0} is isolated in X.

Corollary 1. For every fixed integer n ≥ 0 the following problem can be solved in polynomial time: given a point x_{0} ∈ ℂ^{n} and a constructible set X ⊆ ℂ^{n}, decide whether x_{0} is isolated in X.

Proof. Compute Y = \overline{X − \{x_{0}\}} with the algorithm of Theorem 1, and decide whether x_{0} ∈ Y. Since X is given as a union of m basic constructible X_{1}, …, X_{m}, X −{x_{0}} = ⋃_{1≤i≤m}(X_{i} − {x_{0}}) can be written under the same form by noticing that X_{i} − {x_{0}} is the union of the n basic constructible sets X_{i} ∩ {x_{j} ≠ x_{0,j}} (1 ≤ j ≤ n) where x_{0,1}, …, x_{0,n} are the coordinates of x_{0}.

Note that the algorithms of Theorem 1 and Corollary 1 run in single exponential time when the dimension n is not fixed (this fact will not be used in the rest of the paper). When X is an algebraic variety, Giusti and Heintz [8] have shown that all equidimensional components (and in particular the isolated points) can be computed in single exponential time. Their algorithm is non-uniform. They have further studied the complexity of computing isolated points in [9].

4. NP_{ℂ}-Completeness for Varieties

An instance of CODIM_{ℂ}^{d} consists of a variety V ⊆ ℂ^{n} defined by a system

f_{1}(x) = 0, …, f_{s}(x) = 0 (3)

of polynomial equations. Again, we assume that all polynomials are given in dense representation. An instance is positive if V has an irreducible component of codimension at least d.

Theorem 2. For every d ≥ 0, CODIM_{ℂ}^{d} is NP_{ℂ}-complete.

It will be clear from the proof that this result remains true even if we allow unions of sets of the form (3) as inputs (of course a union of algebraic sets is an algebraic set, but performing the corresponding transformation explicitly may be expensive).

For the bit model of computation we have the following result.

Corollary 2. For every d ≥ 0, CODIM^{d} is NP-hard and if we assume the Generalized Riemann Hypothesis, CODIM^{d} is in AM.

The NP-hardness of CODIM^{d} follows from the same reduction as in the complex model of computation (see below for the details of the complex case). The second part of Corollary 2 is a direct consequence of Theorem 2 and of a general fact ([15], Theorem 5.6).

Theorem 3. Assuming GRH, the boolean part of NP_{ℂ} is included in AM.

The proof goes roughly as follows. Let A be a boolean problem in NP_{ℂ}. We can assume that the corresponding complex machine is parameter-free by the elimination result of [15]. It is thus possible to reduce A to HN in polynomial time in the bit model (this follows basically from the NP_{ℂ}-completeness of HN_{ℂ}). Since HN ∈ AM under GRH (see the long version of [12]), the same is true of A.

Note that if we only want to apply this result to CODIM^{d}, the elimination result of [15] is not needed since the NP_{ℂ} algorithm for CODIM_{ℂ}^{d} exhibited in the proof of Theorem 2 is parameter-free.

The NP_{ℂ}-hardness of CODIM_{ℂ}^{d} follows from a simple reduction from HN_{ℂ} to CODIM_{ℂ}^{d}. To decide whether a system of the form (3) is satisfiable, we introduce d new variables x_{n+1}, …, x_{n+d}. The variety of ℂ^{n+d} defined by

f_{1}(x) = 0, …, f_{s}(x) = 0, x_{n+1} = 0, …, x_{n+d} = 0

is a positive instance of CODIM_{ℂ}^{d} if and only if (3) is satisfiable (indeed, the empty set does not have any irreducible component). If you are uncomfortable with proofs that rely too heavily on the properties of the empty set, write down a system of equations for the variety

{f_{1}(x) = 0, …, f_{s}(x) = 0, x_{n+1} = 0, …, x_{n+d} = 0} ∪ {x_{n+d} = 1},

and you will be convinced that CODIM_{ℂ}^{d} is NP_{ℂ}-hard for d ≥ 2.

The proof that CODIM_{ℂ}^{d} ∈ NP_{ℂ} relies on the Dimension Theorem, a classical result from algebraic geometry ([10], Chapter 1, Proposition 7.1).

Theorem 4. Let U, V ⊆ ℂ^{n} be two irreducible varieties of dimension p and q, respectively. Any irreducible component of U ∩ V has dimension at least p + q − n.

This implies in particular that U ∩ V has dimension at least p + q − n if U ∩ V ≠ ∅.

Proposition 2. Let V ⊆ ℂ^{n} be a nonempty variety. The following properties are equivalent:

(i) There exists an affine subspace E of dimension ≥ d such that V ∩ E has an isolated point.

(ii) There exists an affine subspace E of dimension d such that V ∩E has an isolated

point. (iii) V has an irreducible component of codimension ≥ d.

Proof. We first show that (i) implies (ii). Let E be an affine subspace of dimension ≥ d such that V ∩ E has an isolated point x_{0}. Let F be any d-dimensional subspace of E going through x_{0}. This point is a fortiori isolated in V ∩ F.

Next, we show that (ii) implies (iii), or rather that the negation of (iii) implies the negation of (ii). Let V_{1}, …, V_{r} be the irreducible components of V, and d_{i} = dimV_{i}. If d_{i} ≥ n − d + 1 then by the Dimension Theorem the components of V_{i} ∩ E are of dimension at least 1. It follows that if (ii) does not hold, V ∩ E is a (possibly empty) union of irreducible varieties of dimension at least 1, and therefore has no isolated point.

Finally, to see that (iii) implies (i) let V_{i} be a component of dimension d_{i} ≤ n − d, and E a sufficiently “generic” affine subspace of dimension n−d_{i}. Then V_{i}∩E is finite and nonempty, and moreover for any j ≠ i, (V_{i} ∩ E) ∩ (V_{j} ∩ E) = ∅ (the genericity of E implies directly the first assertion, and also implies the second assertion if we observe that dim(V_{i} ∩ V_{j}) < d_{i} by the irreducibility of V_{i}). Therefore the elements of V_{i} ∩ E are isolated in V ∩ E.

Proof of Theorem 2. The NP_{ℂ} algorithm for CODIM_{ℂ}^{d} is based on the equivalence between (ii) and (iii) in Proposition 2: we guess an affine subspace E of dimension d and decide with the algorithm of Corollary 1 whether V ∩ E has an isolated point. More precisely, we guess a, v_{1}, …, v_{d} ∈ ℂ^{n} and check (in polynomial time) that E = a + Vect(v_{1}, …, v_{d}) has dimension d. Then we obtain a system of equations for V ∩ E in d variables λ_{1}, …, λ_{d} by performing the substitution x = a + ∑_{i=1}^{d} λ_{i}v_{i} in (3). Verifying that V ∩ E has an isolated point requires only polynomial time since the dimension d is fixed. This completes the proof of Theorem 2 since we have already seen that CODIM_{ℂ}^{d} is NP_{ℂ}-hard.

5. Unrestricted Codimension

A most natural question is whether the codimension problem remains in NP_{ℂ} if d is no longer fixed, but rather is part of the input. We shall give strong evidence that this CODIM_{ℂ} problem is unlikely to be in NP_{ℂ} or in coNP_{ℂ}.

Proposition 3. If CODIM_{ℂ} ∈ coNP_{ℂ} then NP_{ℂ} = coNP_{ℂ}.

Proof. CODIM_{ℂ} is NP_{ℂ}-hard since its restrictions CODIM_{ℂ}^{d} are hard. If a NP_{ℂ}-hard problem is in coNP_{ℂ}, this implies that NP_{ℂ} = coNP_{ℂ}.

Proposition 3 can be regarded in its own right as fairly strong evidence that CODIM_{ℂ}∉coNP_{ℂ}, but consider the following.

Proposition 4. If NP_{ℂ} = coNP_{ℂ} then (assuming the generalized Riemann hypothesis) the standard polynomial hierarchy collapses at its second level.

Proof. Let A ⊆ {0, 1}^{∞} be any (standard) coNP problem. Considered as a problem of ℂ^{∞}, A is also coNP_{ℂ}. This problem is therefore in the boolean part of NP_{ℂ} if NP_{ℂ} = coNP_{ℂ}. We conclude by Theorem 3 that coNP ⊆ AM if NP_{ℂ} = coNP_{ℂ}. This is known to imply Σ^{2} = Π^{2} [4, 1].

The evidence that CODIM_{ℂ}∉NP_{ℂ} is almost as strong.

Theorem 5. If CODIM_{ℂ} ∈ NP_{ℂ} then (assuming the generalized Riemann hypothesis) the standard polynomial hierarchy collapses at its second level.

For the proof, we need to introduce several problems of independent interest. An instance of ISO_{ℂ} consists of a variety V defined by a system of polynomial equations as in (3). The instance is positive if V has an isolated point.

If the f_{i}’s are now in ℤ[X_{1}, …, X_{n}] instead of ℂ[X_{1}, …, X_{n}] (and have their coefficients given in bits), we obtain the boolean problem ISO.

An instance of H_{2}N_{ℂ} consists of a system of s homogeneous polynomial equations f_{1} = 0, …, f_{s} = 0 in n + 1 variables x_{1}, …, x_{n+1}. The instance is positive if the f_{i}’s have a non-trivial common zero in ℂ^{n}.

By restricting again to polynomials with integer coefficients, we obtain the boolean problem H_{2}N.

Theorem 6. H_{2}N is NP-hard and ISO is coNP-hard.

Proof. The coNP-hardness of ISO follows immediately from the NP-hardness of H_{2}N. Indeed, a variety defined by a system of homogeneous polynomials has an isolated point (namely, the origin) if and only if these polynomials do not have a non-trivial common zero (i.e., a common zero different from the origin).

It remains to show that H_{2}N is NP-hard. This is done by a reduction from the NPcomplete problem BOOLSYS. An instance of this problem is a system of equations in n boolean variables X_{1}, …, X_{n}. Each equation is of the form X_{i} = T rue, X_{i} = ¬X_{j}, or X_{i} = X_{j} ∨ X_{k}. An instance is positive if it has a satisfying assignment.

Let BS be an instance of BOOLSYS. We shall construct an instance HS of H_{2}N in n + 1 variables x_{1}, …, x_{n+1} such that BS is satisfiable if and only if HS has a non-trivial solution. There are two group of equations in HS. The first group is made of the n equations x_{i}^{2} = x_{n+1}^{2} (1 ≤ i ≤ n). Each equation in the second group is associated to an equation in BS in the following manner. For each equation in BS of the form X_{i} = T rue the equation x_{i} = −x_{n+1} is in HS. To an equation of the form X_{i} = ¬X_{j} we associate the equation x_{i} = −x_{j}, and finally to an equation of the form X_{i} = X_{j} ∨ X_{k} we associate the equation

4x_{i}x_{n+1} = (x_{j} + x_{k})^{2} + 2x_{n+1}(x_{j} + x_{k}) − 4x_{n+1}^{2}.

¿From a system of s boolean equations in n variables we therefore obtain a system of s + n homogeneous equations in n + 1 variables. Assume that BS has a satisfying assignment (X_{1}, …, X_{n}). It is straightforward to check that for any x_{n+1} ≠ 0, if we set x_{i} = −x_{n+1} when X_{i} is true and x_{i} = x_{n+1} when X_{i} is false, (x_{1}, …, x_{n+1}) is a non-trivial solution of HS.

Conversely, assume now that HS has a non-trivial solution (x_{1}, …, x_{n+1}). From the equations in the first group we see that x_{n+1} must be non-zero, and that each x_{i} must be equal to −x_{n+1} or to x_{n+1}. Set X_{i} = T rue if x_{i} = −x_{n+1}, and X_{i} = F alse if x_{i} = x_{n+1}. It is again straightforward to check that (X_{1}, …, X_{n}) is a solution of BS. Since HS can be constructed from BS in polynomial time, we have shown that H_{2}N is NP -hard.

The above proof shows that if we consider only systems of polynomial equations of degree at most 2, the corresponding restrictions of H_{2}N and ISO remain NP-hard and coNP-hard. It turns out that the first part of Theorem 6 can be generalized to arbitrary fields. More precisely, for any field K (of any characteristic) we can consider the problem H_{2}N(K): decide whether a systems of homogeneous equations in n variables (with integer coefficients given in bits) has a solution in K^{n}.

Theorem 7. H_{2}N(K) is NP-hard for every field K.

Proof. One can see that the proof of Theorem 6 is valid for any field of characteristic different from two. Let us therefore assume that K is of characteristic two. In this case, we have to do a variation on the proof of Theorem 6. The n equations of the form x_{i}^{2} = x_{n+1}^{2} in HS are replaced by x_{i}^{2} = x_{i}x_{n+1}. An equation in BS of the form X_{i} = T rue is “simulated” by x_{i} = x_{n+1} in HS. X_{i} = ¬X_{j} is simulated by x_{i} = x_{j} + x_{n+1}, and finally X_{i} = X_{j} ∨ X_{k} is simulated by:

x_{i}^{2} = x_{j}x_{k} + x_{n+1}(x_{j} + x_{k}).

Assume that BS has a satisfying assignment (X_{1}, …, X_{n}). It is straightforward to check that for any x_{n+1} ≠ 0, if we set x_{i} = x_{n+1} when X_{i} is true and x_{i} = 0 when X_{i} is false, (x_{1}, …, x_{n+1}) is a non-trivial solution of HS.

Conversely, assume now that HS has a non-trivial solution (x_{1}, …, x_{n+1}). From the first n equations in HS we see that x_{n+1} must be non-zero, and that each x_{i} must be equal to 0 or to x_{n+1}. Set X_{i} = T rue if x_{i} = x_{n+1}, and X_{i} = F alse if x_{i} = 0. It is again straightforward to check that (X_{1}, …, X_{n}) is a solution of BS. Since HS can be constructed from BS in polynomial time, we have shown that H_{2}N(K) is NP -hard.

Proof of Theorem 5. If CODIM_{ℂ} ∈ NP_{ℂ} then ISO ∈ NP_{ℂ} as well since this problem is just the restriction of CODIM_{ℂ} obtained by setting d = n. If CODIM_{ℂ} ∈ NP_{ℂ}, ISO is therefore in the boolean part of NP_{ℂ}. Since ISO is coNP-hard, we conclude as in the proof of Proposition 3 that coNP ⊆ AM, and the polynomial hierarchy collapses (under GRH).

The same (or simpler) arguments show that by restricting CODIM_{ℂ} to polynomials with integer coefficients given in bits, we obtain a problem which is neither in NP nor coNP, unless NP = coNP.

While CODIM_{ℂ} does not seem to lie in the lower levels of the complex polynomial hierarchy, it is not known whether it belongs to that hierarchy at all. Membership to PH_{ℂ} is in fact open for ISO_{ℂ}, and it is also unknown whether the boolean problem ISO belongs to the standard polynomial hierarchy. Finally, it is not known whether H_{2}N_{ℂ} is NP_{ℂ}-complete.

6. Local Dimensions for Constructible Sets

The goal of this section it to prove the following result.

Theorem 8. For any fixed integer d ≥ 0 the following problem is NP_{ℂ}-complete: given a constructible set X ⊆ ℂ^{n}, decide whether there exists a point x_{0} ∈ X such that dim_{x_{0}}X ≤ n − d.

Proof. NP_{ℂ} hardness is already known from Theorem 2. Here is a NP_{ℂ} algorithm for this problem: guess x_{0} ∈ ℂ^{n}, verify that x_{0} ∈ X and that dim_{x_{0}}X ≤ n − d. By Theorem 9 below, the verification can indeed be performed in polynomial time.

It is not difficult to construct examples of constructible sets for which the NP_{ℂ} algorithm of Theorem 2 fails. As in Corollary 2, it follows from Theorem 8 that for systems with integer coefficients given in bits, the codimension problem for constructible sets is in AM for any fixed d.

The sequel is devoted to the proof of Theorem 9. Let Y ⊆ ℂ^{d} be a constructible set defined by polynomial (in)equations with coefficients in a finitely generated field K ⊆ ℂ. We will use the following characterization of dimension: dimY is the largest transcendence degree over K of any sequence y = (y_{1}, …, y_{d}) such that y ∈ Y.

Theorem 9. For every integer d ≥ 0, the following problem is in P_{ℂ}:

Given a constructible set X ⊆ ℂ^{n} and a point x_{0} ∈ ℂ^{n}, decide whether dim_{x_{0}}X ≤ n − d.

The proof relies on the following fact.

Theorem 10. Let x_{0} be a point of ℂ^{n} and let X ⊆ ℂ^{n} be a constructible set. The two following properties are equivalent.

(i) For a generic d-dimensional linear space E, x_{0} is isolated in X ∩ (x_{0} + E). (ii) dim_{x_{0}}X ≤ n − d.

The proof of Theorem 10 breaks naturally into two parts. We may assume without loss of generality that x_{0} is the origin of ℂ^{n}.

Proposition 5. Let Y be a constructible subset of ℂ^{n}. If dimY ≤ n − d and d ≤ p ≤ n, then dim Y ∩ E ≤ p − d for E in a dense set of p-dimensional linear spaces (in particular, Y ∩ E is finite for E in a dense set of d-dimensional linear spaces).

Proof. There is nothing to prove if Y is finite. Let us therefore assume that dimY ≥ 1, and let K be the subfield of ℂ generated by the parameters of Y. It suffices to show that if A is a (n − p) × n matrix with coefficients that are algebraically independent over K, dim (Y ∩ {Ax = 0}) ≤ p − d. This follows from the fact that if a_{1}, …, a_{n} are algebraically independent over K,

dim(Y ∩ {a_{1}x_{1} + ⋯ + a_{n}x_{n} = 0}) < dim Y.

This fact is a direct consequence of the characterization of dimension in terms of transcendence degree and of Lemma 1 below.

Lemma 1. Assume that a_{1}x_{1} + ⋯ + a_{n}x_{n} = 0 where the a_{i}’s are algebraically independent over K, and x has transcendence degree r > 0 over K. Then x = (x_{1}, …, x_{n}) has transcendence degree at most r − 1 over K(a).

Proof. Assume for instance that x_{1}, …, x_{r} is a transcendence base of K(x) over K. As the a_{i}’s are not algebraically independent over K(x) (because x ≠ 0), they are not algebraically independent over K(x_{1}, …, x_{r}) either. Hence x_{1}, …, x_{r} are not algebraically independent over K(a), and tr.deg_{K(a)}K(x) = tr.deg_{K(a)}K(x_{1}, …, x_{r}) < r.

Proof of Theorem 10. As mentioned previously, we assume that x_{0} = 0. If dim_{x_{0}}X ≤ n − d there exists a Zariski-open set O containing x_{0} such that dimX ∩ O ≤ n − d. Applying Proposition 5 to Y = X ∩ O, we see that X ∩ O ∩ E is finite for E in a dense set of d-dimensional linear spaces. For such an E, x_{0} is isolated in X ∩ O ∩ E and this point is therefore isolated in X ∩ E. This shows that (ii) implies (i).

Conversely, assume now that dim_{x_{0}}X ≥ n − d + 1. Then there exists an irreducible variety V and a strict closed subset W ⊂ V such that x_{0} ∈ V, V \ W ⊆ X and dimV ≥ n − d + 1. Let E be a generic d-dimensional linear space. By the dimension theorem, x_{0} lies on an irreducible component V′ of V ∩ E of dimension at least dimV + d − n. Using now the genericity of E, we see from Proposition 5 that dim W ∩ E ≤ dimW + d − n < dimV′. Since V′ \ (W ∩ E) ⊆ X ∩ E, we conclude that for every Zariski open set O containing x_{0}, dim(X ∩ E) ∩ O ≥ dimV′ ≥ 1, and in particular x_{0} is not isolated in X ∩ E.

We are now ready for the proof of Theorem 9.

Proof. We will in fact describe a BPP_{ℂ} algorithm deciding whether dim_{x_{0}}X ≤ n − d. By Proposition 1, this probabilistic algorithm can be converted into a deterministic algorithm.

The BPP_{ℂ} algorithm is as follows: we take random vectors v_{1}, …, v_{d} ∈ ℂ^{n} and apply Theorem 10 to E = Vect(v_{1}, …, v_{d}). A system of (in)equations for X∩(x_{0}+E) in d new variables λ_{1}, …, λ_{d} is obtained by performing the substitution x = x_{0} + ∑_{i=1}^{d} λ_{i}v_{i} in the systems of the form (1) defining X. This takes polynomial time since d is fixed. By Corollary 1, deciding whether x_{0} is isolated in X ∩ (x_{0} + E) also takes polynomial time for the same reason.

Acknowledgments

A significant part of this work was carried out when the author was visiting the Mathematical Sciences Research Institute. Research at MSRI is supported in part by NSF grant DMS-9701755.

References

[1] L. Babai and S. Moran. Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes. Journal of Computer and System Sciences, 36:254–276, 1988.

[2] L. Blum, F. Cucker, M. Shub, and S. Smale. Complexity and Real Computation. Springer-Verlag, 1998.

[3] L. Blum, M. Shub, and S. Smale. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin of the American Mathematical Society, 21(1):1–46, July 1989.

[4] R. Boppana, J. Håstad, and S. Zachos. Does co-NP have short interactive proofs? Information Processing Letters, 25:127–132, 1987.

[5] O. Chapuis and P. Koiran. Saturation and stability in the theory of computation over the reals. Technical Report 1997/3, Institut Girard Desargues, Université Claude Bernard Lyon I, 1997. To appear in Annals of Pure and Applied Logic.

[6] A. Chistov. Algorithm of polynomial complexity for factoring polynomials and finding the components of varieties in subexponential time. Journal of Soviet Mathematics, 34(4):1838– 1882, 1986. Translated from Zap. Nauchn. Semin. Leningrad. Odtel. Mat. Inst. Steklov (LOMI), 137:124-188, 1984.

[7] A. Chistov. Polynomial-time computation of the dimensions of components of algebraic varieties in zero-characteristic. Journal of Pure and Applied Algebra, 117/118:145–175, 1997.

[8] M. Giusti and J. Heintz. Algorithmes – disons rapides – pour la décomposition d’une variété algébrique en composantes irréductibles et équidimensionnelles. In T. Mora and C. Traverso, editors, Effective Methods in Algebraic Geometry (MEGA’90), Progress in Mathematics 94, pages 169–194. Birkhäuser, 1991.

[9] M. Giusti and J. Heintz. La détermination des points isolés et la dimension d’une variété algébrique peut se faire en temps polynomial. In Computational Algebraic Geometry and Commutative Algebra (Cortona, 1991), pages 216–256. Sympos. Math. XXXIV, Cambridge University Press, 1993.

[10] R. Hartshorne. Algebraic Geometry. Graduate Texts in Mathematics. Springer, 1977.

[11] J. Heintz. Definability and fast quantifier elimination over algebraically closed fields. Theoretical Computer Science, 24:239–277, 1983.

[12] P. Koiran. Hilbert’s Nullstellensatz is in the polynomial hierarchy. Journal of Complexity, 12(4):273–286, 1996. Long version: DIMACS report 96-27.

[13] P. Koiran. Randomized and deterministic algorithms for the dimension of algebraic varieties. In Proc. 38th IEEE Symposium on Foundations of Computer Science, pages 36–45, 1997.

[14] P. Koiran. Elimination of parameters in the polynomial hierarchy. LIP Research Report 98-15, Ecole Normale Supérieure de Lyon, 1998. To appear in Theoretical Computer Science.

[15] J. Kollár. Sharp effective Nullstellensatz. Journal of the AMS, 1:963–975, 1988.

[16] B. Poizat. Les Petits Cailloux. Nur Al-Mantiq Wal-Ma’rifah 3. Aléas, Lyon, 1995.

[17] A. J. Sommese and C. W. Wampler. Numerical algebraic geometry. In J. Renegar, M. Shub, and S. Smale, editors, The Mathematics of Numerical Analysis (Park City, Utah, 1995), pages 749–763. American Mathematical Society, 1996.

LIP, Ecole Normale Supérieure de Lyon – CNRS, 46 allée d’Italie, 69364 Lyon Cedex 07, France

E-mail address: Pascal.Koiran@ens-lyon.fr