ECCC-Report TR09-140https://eccc.weizmann.ac.il/report/2009/140Comments and Revisions published for TR09-140en-usMon, 04 Jan 2010 03:51:10 +0200
Revision 1
| A complex analogue of Toda's Theorem |
Saugata Basu
https://eccc.weizmann.ac.il/report/2009/140#revision1Toda \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.Mon, 04 Jan 2010 03:51:10 +0200https://eccc.weizmann.ac.il/report/2009/140#revision1
Paper TR09-140
| A complex analogue of Toda's Theorem |
Saugata Basu
https://eccc.weizmann.ac.il/report/2009/140Toda \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.Sat, 19 Dec 2009 15:51:58 +0200https://eccc.weizmann.ac.il/report/2009/140