% MSRI preprint. \documentclass[12pt]{amsart} \headheight=8pt \topmargin=0pt \textheight=624pt \textwidth=432pt \oddsidemargin=18pt \evensidemargin=18pt \sloppy \begin{document} \bibliographystyle{plain} \newcommand{\comment}[1]{} \def\trdeg{\mbox{\rm tr.deg}} \def\c{{\mathbb C}} \def\R{{\mathbb R}} \def\q{{\mathbb Q}} \def\n{{\mathbb N}} \def\z{{\mathbb Z}} \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newtheorem{proposition}{Proposition} \newtheorem{corollary}{Corollary} \newtheorem{definition}{Definition} \newtheorem{problem}{Problem} \newtheorem{remark}{Remark} \newtheorem{example}{Example} \newtheorem{hypothesis}{Hypothesis} \def\k{{\mathbb K}} \def\f{{\mathbb F}} \def\P{{\mathbb P}} \def\NP{{\mathbb N \mathbb P}} \def\bp{\mbox{\rm BP}} \def\poly{\mbox{\rm poly}} \def\p{\mbox{\rm P}} \def\rp{\mbox{\rm RP}} \def\bpp{\mbox{\rm BPP}} \def\np{\mbox{\rm NP}} \def\conp{\mbox{\rm coNP}} \def\am{\mbox{\rm AM}} \def\ph{\mbox{\rm PH}} \def\zc{\mbox{\rm ZC}} \def\phc{\mbox{\rm PH}_{\c}} \def\npr{\np_{\R}} \def\npc{\np_{\c}} \def\hn{\mbox{\rm HN}} \def\qbar{\overline{\q}} \def\d{d} \def\nopar{s} \def\dim{\mbox{\rm dim}} \def\cd{\mbox{\rm CODIM}} \def\cdc{\cd_{\c}} \def\proj{\mbox{\rm PROJ}} \def\projr{\proj_{\R}} \def\ff{\mbox{\rm 4FEAS}} \def\ffr{\ff_{\R}} \def\iso{\mbox{\rm ISO}} \def\hhn{\mbox{\rm H}_2\mbox{\rm N}} \def\bsys{\mbox{\rm BOOLSYS}} \title{The Complexity of Local Dimensions \linebreak for Constructible Sets} \author{Pascal Koiran} \address{LIP, Ecole Normale Sup\'erieure de Lyon -- CNRS\\ 46 all\'ee d'Italie\\ 69364 Lyon Cedex 07, France} \email{Pascal.Koiran@ens-lyon.fr} \begin{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. \end{abstract} \maketitle \section{Introduction} It was shown in~\cite{Koi97b} that computing the dimension of algebraic varieties is $\np_{\c}$-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~\cite{SomWam96}). 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 \in \c^n$ and a constructible set $X \subseteq \c^n$, $\dim_{x_0} X$ is $\min \dim (X \cap 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~\cite{Chistov86,Chistov97,GiuHei91} (the first two papers assume a bit model of computation), and~\cite{GiuHei93} for the determination of isolated points. The paper is organized as follows. In section~\ref{prelim} we recall some notions from classical and algebraic complexity theory. In section~\ref{iso_section} 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'' $\cdc^d$: given a variety $V \subseteq \c^n$, decide whether $V$ has an an irreducible component of codimension at least $d$ (i.e., of dimension $\leq n-d$). In section~\ref{varieties} we show that this problem is $\np_{\c}$-complete for any fixed $d$. If $V$ is defined by polynomial equations with integer coefficients given in bits, the corresponding $\cd^d$ problem is $\np$-hard, and belongs to $\am$ (assuming GRH). In section~\ref{unrestricted} 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_{\c}$ or $\conp_{\c}$. 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_{\c} = \conp_{\c}$ would imply the collapse of the polynomial hierarchy to its second level. Section~\ref{unrestricted} ends with a few open problems. Finally, the results of section~\ref{varieties} are generalized to arbitrary constructible sets in section~\ref{cons_section} (algebraic varieties are treated separately in section~\ref{varieties} because there is a simpler algorithm in that case). \section{Complexity of Computations} \label{prelim} We recall that $\p_{\c}$ denotes the class of problems of $\c^{\infty}$ which can be solved in polynomial time in the Blum-Shub-Smale model of computation over the complex numbers~\cite{BSS89}. Roughly speaking, a problem $A \subseteq \c^{\infty}$ is in $\p_{\c}$ if there is an algorithm which on any input $x \in \c^n$ can decide whether $x \in 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~\cite{bcss,ChaKoi,Poizat95}. We also recall that $A$ is in $\np_{\c}$ if there exists a polynomial $p(n)$ and a problem $B \in \p_{\c}$ such that for all $x \in \c^n$, $x \in A$ if and only if there exists $y \in \c^{p(n)}$ such that $(x_1,\ldots,x_n,y_1,\ldots,y_{p(n)}) \in B$. One can define the higher levels of the polynomial hierarchy over $\c$ in a similar way (they will not be used in this paper). As in the classical case, there are natural $\np_{\c}$-complete problems. Perhaps the simplest example is Hilbert's Nullstellensatz ($\hn_{\c}$): 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~\cite{Koi96d}. $\am$ is a randomized version of $\np$ which is located in the second level of the polynomial hierarchy (i.e., $\np \subseteq \am \subseteq \Pi_2$). There is also a notion of randomization over $\c$: a problem $A \subseteq \c^{\infty}$ is said to be in $\bpp_{\c}$ if there exists a polynomial $p(n)$ and a problem $B \in \p_{\c}$ such that for all $x \in \c^n$, $x \in A$ if and only if the set of $y \in \c^{p(n)}$ such that $(x_1,\ldots,x_n,y_1,\ldots,y_{p(n)}) \in B$ is Zariski dense in $\c^{p(n)}$. However, the situation seems to be dramatically different from the classical case: \begin{proposition} \label{bpp} $\bpp_{\c} = \p_{\c}$. \end{proposition} For a proof see~\cite{Koi98a}, 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_{\c}$ 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). \newpage \section{Isolated Points} \label{iso_section} We assume that a constructible set $X \subseteq \c^n$ is given as a union of basic constructible sets $X_1,\ldots,X_m$. Each $X_i$ is described by a system of polynomial equalities of inequalities: \begin{equation} \label{system} f_{i,1}(x)=0,\ldots,f_{i,s_i}(x)=0;\ g_{i,1}(x) \neq 0,\ldots,g_{i,t_i}(x) \neq 0. \end{equation} All polynomials are given in dense representation. In the sequel, $D \geq 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$). \begin{theorem} \label{closure} For every fixed integer $n \geq 0$, the Zariski closure $\overline{X}$ of $X$ can be computed in polynomial time. \end{theorem} \begin{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,\ldots,f_s(x)=0;\ g(x) \neq 0.$$ Note that if there are several inequalities $g_1 (x) \neq 0,\ldots,g_t(x) \neq 0$ in the system, they can be replaced by $g(x) \neq 0$ where $g$ is the product of the $g_i$'s. Now we follow closely Giusti and Heintz (\cite{GiuHei91}, Proposition 4.2.5), working out the bounds in greater detail. Let $V = \{x \in \c^n;\ f_1(x)=0,\ldots,f_s(x)=0\}$, $W = \{x \in \c^n;\ g(x)=0\}$, and let $E'$ be the finite-dimensional vector space of polynomials $f \in \c[x_1,\ldots,x_n]$ such that there exist polynomials $p_1,\ldots,p_s \in \c[x_1,\ldots,x_n]$ satisfying $\deg(p_i f_i) \leq D^n(D^n+2D+1)$ and \begin{equation} \label{hn} f\cdot g^{D^n} = \sum_{i=1}^s p_i f_i. \end{equation} 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} \subseteq V(E')$, where $V(E')$ is the algebraic set defined by $E'$. Since $V(E')$ is closed, it suffices to show that $X \subseteq V(E')$. Let $x \in X$ and $f \in E'$. Since $f_1(x)=\cdots=f_s(x)=0$ and $g(x) \neq 0$, it follows from~(\ref{hn}) that $f(x)=0$. Since this holds for an arbitrary $f \in E'$, we conclude that $x \in V(E')$. Let us now establish the converse inclusion $V(E') \subseteq \overline{X}$. By Proposition 3 from~\cite{Heintz83}, $\overline{X}$ can be defined by $n+1$ polynomials $f'_1,\ldots,f'_{n+1}$ of degree bounded by $\deg(\overline{X})$, and $\deg(\overline{X}) \leq \deg(V) \leq 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~\cite{kollar} there exist polynomials $p_1,\ldots,p_s$ with $\deg(p_i f_i) \leq D^n(D^n+D+1)$ and an integer $k \leq D^n$ such that $$(f'_jg)^k = \sum_{i=1}^s p_i f_i.$$ This can be rewritten as: $${f'}^k g^{D^n} = \sum_{i=1}^s g ^{D^n-k} p_i f_i,$$ and since $\deg(g ^{D^n-k}p_i f_i) \leq D^n(D^n+D+1)+D^{n+1}$ we conclude that ${f'_j}^k \in E'$. Hence $f'_j$ vanishes on $V(E')$. Since this holds for all $j=1,\ldots,n+1$, we conclude that $V(E') \subseteq \overline{X}$. This completes the proof of the claim, and of the theorem. \end{proof} In the above proof, the coefficients of $g=\prod_{1 \leq i \leq t} g_i$ can be computed from the coefficients of the $g_i$'s by computing iteratively $\prod_{2 \leq i \leq 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 ${Dt+n \choose 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~\ref{cdc} and Theorem~\ref{cons}. We say that a point $x_0 \in \c^n$ is isolated in $X$ if there exists a Zariski open set $O$ containing $x_0$ such that $(X - \{x_0\}) \cap O = \emptyset$, or equivalently if $x_0 {\not \in} \overline{X - \{x_0\}}$. Note that if $x_0$ is not isolated in $X$, this does not necessarily implies that $x_0 \in X$. Of course, we say that $X$ has an isolated point if there exists a point $x_0 \in X$ such that $x_0$ is isolated in $X$. \begin{corollary} \label{isotest} For every fixed integer $n \geq 0$ the following problem can be solved in polynomial time: given a point $x_0 \in \c^n$ and a constructible set $X \subseteq \c^n$, decide whether $x_0$ is isolated in $X$. \end{corollary} \begin{proof} Compute $Y= \overline{X - \{x_0\}}$ with the algorithm of Theorem~\ref{closure}, and decide whether $x_0 \in Y$. Since $X$ is given as a union of $m$ basic constructible $X_1,\ldots,X_m$, $X-\{x_0\} = \bigcup_{1 \leq i \leq 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 \cap \{x_j \neq x_{0,j}\}$ ($1 \leq j \leq n$) where $x_{0,1},\ldots,x_{0,n}$ are the coordinates of $x_0$. \end{proof} Note that the algorithms of Theorem~\ref{closure} and Corollary~\ref{isotest} 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~\cite{GiuHei91} 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~\cite{GiuHei93}. \newpage \section{$\npc$-Completeness for Varieties} \label{varieties} An instance of $\cdc^d$ consists of a variety $V \subseteq \c^n$ defined by a system \begin{equation} \label{system2} f_1(x)=0, \ldots,f_s(x)=0 \end{equation} 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$. \begin{theorem} \label{cdc} For every $d \geq 0$, $\cdc^d$ is $\npc$-complete. \end{theorem} It will be clear from the proof that this result remains true even if we allow unions of sets of the form~(\ref{system2}) 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. \begin{corollary} \label{boolean} For every $d \geq 0$, $\cd^d$ is NP-hard and if we assume the Generalized Riemann Hypothesis, $\cd^d$ is in $\am$. \end{corollary} The NP-hardness of $\cd^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~\ref{boolean} is a direct consequence of Theorem~\ref{cdc} and of a general fact (\cite{Koi98a}, Theorem 5.6). \begin{theorem} \label{cd} Assuming GRH, the boolean part of $\np_{\c}$ is included in $\am$. \end{theorem} The proof goes roughly as follows. Let $A$ be a boolean problem in $\npc$. We can assume that the corresponding complex machine is parameter-free by the elimination result of~\cite{Koi98a}. It is thus possible to reduce $A$ to $\hn$ in polynomial time in the bit model (this follows basically from the $\npc$-completeness of $\hn_{\c}$). Since $\hn \in \am$ under GRH (see the long version of~\cite{Koi96d}), the same is true of $A$. Note that if we only want to apply this result to $\cd^d$, the elimination result of~\cite{Koi98a} is not needed since the $\npc$ algorithm for $\cdc^d$ exhibited in the proof of Theorem~\ref{cdc} is parameter-free. The $\npc$-hardness of $\cdc^d$ follows from a simple reduction from $\hn_{\c}$ to $\cdc^d$. To decide whether a system of the form~(\ref{system2}) is satisfiable, we introduce $d$ new variables $x_{n+1},\ldots,x_{n+d}$. The variety of $\c^{n+d}$ defined by $$f_1(x)=0, \ldots,f_s(x)=0,x_{n+1}=0,\ldots,x_{n+d}=0$$ is a positive instance of $\cdc^d$ if and only if~(\ref{system2}) 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, \ldots,f_s(x)=0,x_{n+1}=0,\ldots,x_{n+d}=0\} \cup \{x_{n+d}=1\},$$ and you will be convinced that $\cdc^d$ is $\np_{\c}$-hard for $d \geq 2$. The proof that $\cdc^d \in \npc$ relies on the Dimension Theorem, a classical result from algebraic geometry~(\cite{Hart}, Chapter 1, Proposition~7.1). \begin{theorem} Let $U,V \subseteq \c^n$ be two irreducible varieties of dimension $p$ and $q$, respectively. Any irreducible component of $U \cap V$ has dimension at least $p+q-n$. \end{theorem} This implies in particular that $U \cap V$ has dimension at least $p+q-n$ if $U \cap V \neq \emptyset$. \begin{proposition} \label{inter} Let $V \subseteq \c^n$ be a nonempty variety. The following properties are equivalent: \begin{itemize} \item[(i)] There exists an affine subspace $E$ of dimension $\geq d$ such that $V \cap E$ has an isolated point. \item[(ii)] There exists an affine subspace $E$ of dimension $d$ such that $V \cap E$ has an isolated point. \item[(iii)] $V$ has an irreducible component of codimension $\geq d$. \end{itemize} \end{proposition} \begin{proof} We first show that (i) implies (ii). Let $E$ be an affine subspace of dimension $\geq d$ such that $V \cap E$ has an isolated point $x_0$. Let $F$ be any $d$-dimensional subspace of $E$ going through $x_0$. This point is {\em a fortiori} isolated in $V \cap F$. Next, we show that (ii) implies (iii), or rather that the negation of (iii) implies the negation of (ii). Let $V_1,\ldots,V_r$ be the irreducible components of $V$, and $d_i = \dim V_i$. If $d_i \geq n-d+1$ then by the Dimension Theorem the components of $V_i \cap E$ are of dimension at least 1. It follows that if (ii) does not hold, $V \cap 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 \leq n-d$, and $E$ a sufficiently ``generic'' affine subspace of dimension $n-d_i$. Then $V_i \cap E$ is finite and nonempty, and moreover for any $j \neq i$, $(V_i \cap E) \cap (V_j \cap E) = \emptyset$ (the genericity of $E$ implies directly the first assertion, and also implies the second assertion if we observe that $\dim (V_i \cap V_j) < d_i$ by the irreducibility of $V_i$). Therefore the elements of $V_i \cap E$ are isolated in $V \cap E$. \end{proof} \begin{proof}[ Proof of Theorem~\ref{cdc}] The $\np_{\c}$ algorithm for $\cdc^d$ is based on the equivalence between (ii) and (iii) in Proposition~\ref{inter}: we guess an affine subspace $E$ of dimension $d$ and decide with the algorithm of Corollary~\ref{isotest} whether $V \cap E$ has an isolated point. More precisely, we guess $a,v_1,\ldots,v_d \in \c^n$ and check (in polynomial time) that $E=a+\mbox{\rm Vect}(v_1,\ldots,v_d)$ has dimension $d$. Then we obtain a system of equations for $V \cap E$ in $d$ variables $\lambda_1,\ldots,\lambda_d$ by performing the substitution $x=a+\sum_{i=1}^d \lambda_i v_i$ in~(\ref{system2}). Verifying that $V \cap E$ has an isolated point requires only polynomial time since the dimension $d$ is fixed. This completes the proof of Theorem~\ref{cdc} since we have already seen that $\cdc^d$ is $\np_{\c}$-hard. \end{proof} \section{Unrestricted Codimension} \label{unrestricted} A most natural question is whether the codimension problem remains in $\np_{\c}$ if $d$ is no longer fixed, but rather is part of the input. We shall give strong evidence that this $\cdc$ problem is unlikely to be in $\np_{\c}$ or in $\conp_{\c}$. \begin{proposition} \label{conp} If $\cdc \in \conp_{\c}$ then $\np_{\c} = \conp_{\c}$. \end{proposition} \begin{proof} $\cdc$ is $\np_{\c}$-hard since its restrictions $\cdc^d$ are hard. If a $\np_{\c}$-hard problem is in $\conp_{\c}$, this implies that $\np_{\c} = \conp_{\c}$. \end{proof} Proposition~\ref{conp} can be regarded in its own right as fairly strong evidence that $\cdc {\not \in} \conp_{\c}$, but consider the following. \begin{proposition} If $\np_{\c} = \conp_{\c}$ then (assuming the generalized Riemann hypothesis) the standard polynomial hierarchy collapses at its second level. \end{proposition} \begin{proof} Let $A \subseteq \{0,1\}^{\infty}$ be any (standard) $\conp$ problem. Considered as a problem of ${\c}^{\infty}$, $A$ is also $\conp_{\c}$. This problem is therefore in the boolean part of ${\np}_{\c}$ if $\np_{\c} = \conp_{\c}$. We conclude by Theorem~\ref{cd} that $\conp \subseteq \am$ if $\np_{\c} = \conp_{\c}$. This is known to imply $\Sigma^2 = \Pi^2$~\cite{BHZ,BabMo88}. \end{proof} The evidence that $\cdc {\not \in} \np_{\c}$ is almost as strong. \begin{theorem} \label{np} If $\cdc \in \np_{\c}$ then (assuming the generalized Riemann hypothesis) the standard polynomial hierarchy collapses at its second level. \end{theorem} For the proof, we need to introduce several problems of independent interest. An instance of $\iso_{\c}$ consists of a variety $V$ defined by a system of polynomial equations as in~(\ref{system2}). The instance is positive if $V$ has an isolated point. If the $f_i$'s are now in $\z[X_1,\ldots,X_n]$ instead of $\c[X_1,\ldots,X_n]$ (and have their coefficients given in bits), we obtain the boolean problem $\iso$. An instance of $\hhn_{\c}$ consists of a system of $s$ homogeneous polynomial equations $f_1 =0,\ldots,f_s=0$ in $n+1$ variables $x_1,\ldots,x_{n+1}$. The instance is positive if the $f_i$'s have a non-trivial common zero in $\c^n$. By restricting again to polynomials with integer coefficients, we obtain the boolean problem $\hhn$. \begin{theorem} \label{hard} $\hhn$ is $\np$-hard and $\iso$ is $\conp$-hard. \end{theorem} \begin{proof} The $\conp$-hardness of $\iso$ follows immediately from the $\np$-hardness of $\hhn$. 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 $\hhn$ is $\np$-hard. This is done by a reduction from the NP-complete problem $\bsys$. An instance of this problem is a system of equations in $n$ boolean variables $X_1,\ldots,X_n$. Each equation is of the form $X_i = True$, $X_i = \neg X_j$, or $X_i = X_j \vee X_k$. An instance is positive if it has a satisfying assignment. Let $BS$ be an instance of $\bsys$. We shall construct an instance $HS$ of $\hhn$ in $n+1$ variables $x_1,\ldots,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 \leq i \leq 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 = True$ the equation $x_i = - x_{n+1}$ is in $HS$. To an equation of the form $X_i = \neg X_j$ we associate the equation $x_i = - x_j$, and finally to an equation of the form $X_i = X_j \vee X_k$ we associate the equation $$4x_i x_{n+1} = (x_j+x_k)^2 + 2 x_{n+1} (x_j+x_k) - 4 x_{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,\ldots,X_n)$. It is straightforward to check that for any $x_{n+1} \neq 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,\ldots,x_{n+1})$ is a non-trivial solution of $HS$. Conversely, assume now that $HS$ has a non-trivial solution $(x_1,\ldots,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=True$ if $x_i = -x_{n+1}$, and $X_i = False$ if $x_i = x_{n+1}$. It is again straightforward to check that $(X_1,\ldots,X_n)$ is a solution of $BS$. Since $HS$ can be constructed from $BS$ in polynomial time, we have shown that $\hhn$ is $NP$-hard. \end{proof} The above proof shows that if we consider only systems of polynomial equations of degree at most 2, the corresponding restrictions of $\hhn$ and $\iso$ remain $\np$-hard and $\conp$-hard. It turns out that the first part of Theorem~\ref{hard} can be generalized to arbitrary fields. More precisely, for any field $K$ (of any characteristic) we can consider the problem $\hhn(K)$: decide whether a systems of homogeneous equations in $n$ variables (with integer coefficients given in bits) has a solution in $K^n$. \begin{theorem} $\hhn(K)$ is $\np$-hard for every field $K$. \end{theorem} \begin{proof} One can see that the proof of Theorem~\ref{hard} 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~\ref{hard}. 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 = True$ is ``simulated'' by $x_i = x_{n+1}$ in $HS$. $X_i = \neg X_j$ is simulated by $x_i = x_j+x_{n+1}$, and finally $X_i = X_j \vee 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,\ldots,X_n)$. It is straightforward to check that for any $x_{n+1} \neq 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,\ldots,x_{n+1})$ is a non-trivial solution of $HS$. Conversely, assume now that $HS$ has a non-trivial solution $(x_1,\ldots,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=True$ if $x_i = x_{n+1}$, and $X_i = False$ if $x_i = 0$. It is again straightforward to check that $(X_1,\ldots,X_n)$ is a solution of $BS$. Since $HS$ can be constructed from $BS$ in polynomial time, we have shown that $\hhn(K)$ is $NP$-hard. \end{proof} \begin{proof}[Proof of Theorem~\ref{np}] If $\cdc \in \np_{\c}$ then $\iso \in \np_{\c}$ as well since this problem is just the restriction of $\cdc$ obtained by setting $d=n$. If $\cdc \in \np_{\c}$, $\iso$ is therefore in the boolean part of $\np_{\c}$. Since $\iso$ is $\conp$-hard, we conclude as in the proof of Proposition~\ref{conp} that $\conp \subseteq \am$, and the polynomial hierarchy collapses (under GRH). \end{proof} The same (or simpler) arguments show that by restricting $\cdc$ to polynomials with integer coefficients given in bits, we obtain a problem which is neither in $\np$ nor $\conp$, unless $\np=\conp$. While $\cdc$ 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_{\c}$ is in fact open for $\iso_{\c}$, and it is also unknown whether the boolean problem $\iso$ belongs to the standard polynomial hierarchy. Finally, it is not known whether $\hhn_{\c}$ is $\np_{\c}$-complete. \section{Local Dimensions for Constructible Sets} \label{cons_section} The goal of this section it to prove the following result. \begin{theorem} \label{conscodim} For any fixed integer $d \geq 0$ the following problem is $\np_{\c}$-complete: given a constructible set $X \subseteq \c^n$, decide whether there exists a point $x_0 \in X$ such that $\dim_{x_0} X \leq n-d$. \end{theorem} \begin{proof} $\np_{\c}$ hardness is already known from Theorem~\ref{cdc}. Here is a $\np_{\c}$ algorithm for this problem: guess $x_0 \in \c^n$, verify that $x_0 \in X$ and that $\dim_{x_0} X \leq n-d$. By Theorem~\ref{cons} below, the verification can indeed be performed in polynomial time. \end{proof} It is not difficult to construct examples of constructible sets for which the $\np_{\c}$ algorithm of Theorem~\ref{cdc} fails. As in Corollary~\ref{boolean}, it follows from Theorem~\ref{conscodim} 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~\ref{cons}. Let $Y \subseteq \c^d$ be a constructible set defined by polynomial (in)equations with coefficients in a finitely generated field $K \subseteq \c$. We will use the following characterization of dimension: $\dim Y$ is the largest transcendence degree over $K$ of any sequence $y=(y_1,\ldots,y_d)$ such that $y \in Y$. \begin{theorem} \label{cons} For every integer $d \geq 0$, the following problem is in $\p_{\c}$: Given a constructible set $X \subseteq \c^n$ and a point $x_0 \in \c^n$, decide whether $\dim_{x_0} X \leq n-d$. \end{theorem} The proof relies on the following fact. \begin{theorem} \label{iso} Let $x_0$ be a point of $\c^n$ and let $X \subseteq \c^n$ be a constructible set. The two following properties are equivalent. \begin{itemize} \item[(i)] For a generic $d$-dimensional linear space $E$, $x_0$ is isolated in $X \cap (x_0+E)$. \item[(ii)] $\dim_{x_0} X \leq n-d$. \end{itemize} \end{theorem} The proof of Theorem~\ref{iso} breaks naturally into two parts. We may assume without loss of generality that $x_0$ is the origin of $\c^n$. \begin{proposition} \label{smalldim} Let $Y$ be a constructible subset of $\c^n$. If $\dim Y \leq n-d$ and $d \leq p \leq n$, then $\dim\ Y \cap E \leq p-d$ for $E$ in a dense set of $p$-dimensional linear spaces (in particular, $Y \cap E$ is finite for $E$ in a dense set of $d$-dimensional linear spaces). \end{proposition} \begin{proof} There is nothing to prove if $Y$ is finite. Let us therefore assume that $\dim Y \geq 1$, and let $K$ be the subfield of $\c$ generated by the parameters of $Y$. It suffices to show that if $A$ is a $(n-p) \times n$ matrix with coefficients that are algebraically independent over $K$, $\dim\ (Y \cap \{Ax=0\}) \leq p-d$. This follows from the fact that if $a_1,\ldots,a_n$ are algebraically independent over $K$, $$\dim (Y \cap \{a_1x_1+\cdots+a_nx_n=0\}) < \dim\, Y.$$ This fact is a direct consequence of the characterization of dimension in terms of transcendence degree and of Lemma~\ref{hyperplane} below. \end{proof} \begin{lemma} \label{hyperplane} Assume that $a_1x_1+\cdots+a_nx_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,\ldots,x_n)$ has transcendence degree at most $r-1$ over $K(a)$. \end{lemma} \begin{proof} Assume for instance that $x_1,\ldots,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 \neq 0$), they are not algebraically independent over $K(x_1,\ldots,x_r)$ either. Hence $x_1,\ldots,x_r$ are not algebraically independent over $K(a)$, and $\trdeg_{K(a)}K(x)=\trdeg_{K(a)}K(x_1,\ldots,x_r)