Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR09-140 | 4th January 2010 03:51

A complex analogue of Toda's Theorem

RSS-Feed




Revision #1
Authors: Saugata Basu
Accepted on: 4th January 2010 03:51
Downloads: 1688
Keywords: 


Abstract:

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.



Changes to previous version:

More details added; errors corrected.


Paper:

TR09-140 | 18th December 2009 01:15

A complex analogue of Toda's Theorem





TR09-140
Authors: Saugata Basu
Publication: 19th December 2009 15:51
Downloads: 1748
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint