Toda \cite{Toda} proved in 1989 that the (discrete) polynomial time hierarchy,

$\mathbf{PH}$,

is contained in the class $\mathbf{P}^{\#\mathbf{P}}$,

namely the class of languages that can be

decided by a Turing machine in polynomial time given access to an

oracle with the power to compute a function in the counting complexity

class $\#\mathbf{P}$. This result which illustrates the power of counting

is considered to be a seminal result in computational complexity theory.

An analogous result (with a compactness hypothesis)

in the complexity theory over the reals

(in the sense of

Blum-Shub-Smale real Turing machines \cite{BSS89})

was proved in \cite{BZ09}.

Unlike Toda's proof in the discrete case, which relied

on sophisticated combinatorial arguments, the proof in \cite{BZ09}

is topological in nature in which the properties of the topological join

is used in a fundamental way. However, the constructions used in

\cite{BZ09} was semi-algebraic in nature -- they used real inequalities in an

essential way and as such do not extend to the complex case.

In this paper, we extend the techniques

developed in \cite{BZ09} to the complex case. A key role is played by

the complex join of quasi-projective complex varieties.

As a consequence we obtain a complex analogue of Toda's theorem. As in the

real case, the complex analogue of Toda's theorem is proved with a compactness

assumption which we are unable to remove presently.

We also relate the computational hardness

of two well-studied problems in algorithmic complex geometry

-- namely the problem of deciding sentences in the first order theory

of algebraically closed fields of characteristic $0$

with a constant number of quantifier alternations,

and that of computing Betti numbers of constructible sets.

We obtain a polynomial time reduction in the Blum-Shub-Smale model

of the compact version of the

first problem to the second.

More details added; errors corrected.

Toda \cite{Toda} proved in 1989 that the (discrete) polynomial time hierarchy,

$\mathbf{PH}$,

is contained in the class $\mathbf{P}^{\#\mathbf{P}}$,

namely the class of languages that can be

decided by a Turing machine in polynomial time given access to an

oracle with the power to compute a function in the counting complexity

class $\#\mathbf{P}$. This result which illustrates the power of counting

is considered to be a seminal result in computational complexity theory.

An analogous result (with a compactness hypothesis)

in the complexity theory over the reals

(in the sense of

Blum-Shub-Smale real Turing machines \cite{BSS89})

was proved in \cite{BZ09}.

Unlike Toda's proof in the discrete case, which relied

on sophisticated combinatorial arguments, the proof in \cite{BZ09}

is topological in nature in which the properties of the topological join

is used in a fundamental way. However, the constructions used in

\cite{BZ09} was semi-algebraic in nature -- they used real inequalities in an

essential way and as such do not extend to the complex case.

In this paper, we extend the techniques

developed in \cite{BZ09} to the complex case. A key role is played by

the complex join of quasi-projective complex varieties.

As a consequence we obtain a complex analogue of Toda's theorem. As in the

real case, the complex analogue of Toda's theorem is proved with a compactness

assumption which we are unable to remove presently.

We also relate the computational hardness

of two well-studied problems in algorithmic complex geometry

-- namely the problem of deciding sentences in the first order theory

of algebraically closed fields of characteristic $0$

with a constant number of quantifier alternations,

and that of computing Betti numbers of constructible sets.

We obtain a polynomial time reduction in the Blum-Shub-Smale model

of the compact version of the

first problem to the second.