% 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)<r$.
\end{proof}

\begin{proof}[Proof of Theorem~\ref{iso}]
As mentioned previously, we assume that $x_0=0$.
If $\dim_{x_0} X \leq n-d$ there exists a Zariski-open set 
$O$ containing $x_0$ such that $\dim X \cap O \leq n-d$.
Applying Proposition~\ref{smalldim} to $Y = X \cap O$, 
we see that $X \cap O \cap E$ is finite for $E$ in a dense set of 
$d$-dimensional linear spaces. 
For such an $E$, $x_0$ is isolated in $X \cap O \cap E$ 
and this point is therefore isolated in $X \cap E$.
This shows that (ii) implies (i).


Conversely, assume now that $\dim_{x_0} X \geq n-d+1$. 
Then there exists an irreducible variety $V$ and a strict closed subset 
$W \subset V$ such that $x_0 \in V$, $V \setminus W \subseteq X$ and
$\dim V \geq 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 \cap E$
of dimension at least $\dim V + d -n$.
Using now the genericity of $E$, 
we see from Proposition~\ref{smalldim} that 
$\dim\ W \cap E \leq \dim W + d -n < \dim V'$.
Since $V' \setminus (W \cap E) \subseteq X \cap E$,
we conclude that for every Zariski open set $O$ containing~$x_0$,
$\dim (X \cap E) \cap O \geq \dim V' \geq 1$, 
and in particular $x_0$ is not isolated in $X \cap E$.
\end{proof}
We are now ready for the proof of Theorem~\ref{cons}.
\begin{proof} 
We will in fact describe a $\bpp_{\c}$ algorithm deciding whether
$\dim_{x_0} X \leq n-d$. By Proposition~\ref{bpp}, 
this probabilistic algorithm can be converted into a deterministic algorithm.

The $\bpp_{\c}$ algorithm is as follows: we take random vectors 
$v_1,\ldots,v_d \in \c^n$ and apply Theorem~\ref{iso} to 
$E=\mbox{\rm Vect}(v_1,\ldots,v_d)$. 
A system of (in)equations for $X \cap (x_0+E)$ in $d$ new variables
 $\lambda_1,\ldots,\lambda_d$ is obtained by performing the substitution
$x=x_0+\sum_{i=1}^d \lambda_i v_i$ in the systems of the form~(\ref{system})
defining $X$.
This takes  polynomial time since $d$ is fixed.
By Corollary~\ref{isotest}, deciding whether $x_0$ is isolated in $X \cap (x_0+E)$ 
also takes polynomial time for the same reason.
\end{proof}

\section*{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.

\newpage

\begin{thebibliography}{10}

\bibitem{BabMo88}
L.~Babai and S.~Moran.
\newblock {Arthur-Merlin} games: A randomized proof system, and a hierarchy of
  complexity classes.
\newblock {\em Journal of Computer and System Sciences}, 36:254--276, 1988.

\bibitem{bcss}
L.~Blum, F.~Cucker, M.~Shub, and S.~Smale.
\newblock {\em Complexity and Real Computation}.
\newblock Springer-Verlag, 1998.

\bibitem{BSS89}
L.~Blum, M.~Shub, and S.~Smale.
\newblock On a theory of computation and complexity over the real numbers:
  {NP}-completeness, recursive functions and universal machines.
\newblock {\em Bulletin of the {American} Mathematical Society}, 21(1):1--46,
  July 1989.

\bibitem{BHZ}
R.~Boppana, J.~H{\aa}stad, and S.~Zachos.
\newblock Does {co-NP} have short interactive proofs?
\newblock {\em Information Processing Letters}, 25:127--132, 1987.

\bibitem{ChaKoi}
O.~Chapuis and P.~Koiran.
\newblock Saturation and stability in the theory of computation over the reals.
\newblock Technical Report 1997/3, Institut Girard Desargues, Universit\'e
  Claude Bernard Lyon I, 1997.
\newblock To appear in {\em Annals of Pure and Applied Logic}.

\bibitem{Chistov86}
A.~Chistov.
\newblock Algorithm of polynomial complexity for factoring polynomials and
  finding the components of varieties in subexponential time.
\newblock {\em Journal of Soviet Mathematics}, 34(4):1838--1882, 1986.
\newblock Translated from {\em Zap. Nauchn. Semin. Leningrad. Odtel. Mat. Inst.
  Steklov (LOMI)}, 137:124-188, 1984.

\bibitem{Chistov97}
A.~Chistov.
\newblock Polynomial-time computation of the dimensions of components of
  algebraic varieties in zero-characteristic.
\newblock {\em Journal of Pure and Applied Algebra}, 117/118:145--175, 1997.

\bibitem{GiuHei91}
M.~Giusti and J.~Heintz.
\newblock Algorithmes -- disons rapides -- pour la d\'ecomposition d'une
  vari\'et\'e alg\'ebrique en composantes irr\'eductibles et
  \'equidimensionnelles.
\newblock In T.~Mora and C.~Traverso, editors, {\em Effective Methods in
  Algebraic Geometry (MEGA'90)}, Progress in Mathematics { 94}, pages 169--194.
  Birkh\"auser, 1991.

\bibitem{GiuHei93}
M.~Giusti and J.~Heintz.
\newblock La d\'etermination des points isol\'es et la dimension d'une
  vari\'et\'e alg\'ebrique peut se faire en temps polynomial.
\newblock In {\em Computational Algebraic Geometry and Commutative Algebra
  (Cortona, 1991)}, pages 216--256. Sympos. Math. XXXIV, Cambridge University
  Press, 1993.

\bibitem{Hart}
R.~Hartshorne.
\newblock {\em Algebraic Geometry}.
\newblock Graduate Texts in Mathematics. Springer, 1977.

\bibitem{Heintz83}
J.~Heintz.
\newblock Definability and fast quantifier elimination over algebraically
  closed fields.
\newblock {\em Theoretical Computer Science}, 24:239--277, 1983.

\bibitem{Koi96d}
P.~Koiran.
\newblock {Hilbert's Nullstellensatz} is in the polynomial hierarchy.
\newblock {\em Journal of Complexity}, 12(4):273--286, 1996.
\newblock Long version: DIMACS report 96-27.


\bibitem{Koi97b}
P.~Koiran.
\newblock Randomized and deterministic algorithms for the dimension of
  algebraic varieties.
\newblock In {\em Proc. 38th IEEE Symposium on Foundations of Computer
  Science}, pages 36--45, 1997.

\bibitem{Koi98a}
P.~Koiran.
\newblock Elimination of parameters in the polynomial hierarchy.
\newblock LIP Research Report 98-15, Ecole Normale Sup\'erieure de Lyon, 1998.
\newblock To appear in {\em Theoretical Computer Science}.

\bibitem{kollar}
J.~Koll\'ar.
\newblock Sharp effective {Nullstellensatz}.
\newblock {\em Journal of the AMS}, 1:963--975, 1988.

\bibitem{Poizat95}
B.~Poizat.
\newblock {\em Les Petits Cailloux}.
\newblock Nur Al-Mantiq Wal-Ma'rifah {\bf 3}. Al\'eas, Lyon, 1995.

\bibitem{SomWam96}
A.~J. Sommese and C.~W. Wampler.
\newblock Numerical algebraic geometry.
\newblock In J.~Renegar, M.~Shub, and S.~Smale, editors, {\em The Mathematics
  of Numerical Analysis (Park City, Utah, 1995)}, pages 749--763. American
  Mathematical Society, 1996.

\end{thebibliography}


\end{document}
