Polynomial hierarchy, Betti numbers and a real analogue of Toda's theorem

Details Polynomial hierarchy, Betti numbers and a real analogue of Toda's theorem Polynomial hierarchy, Betti numbers and a real analogue of Toda's theorem

2008-12-05

arxiv.org/abs/0812.1200v3

Found. Comput. Math, 10:429-454, 2010

Computer Science

Computational Complexity

Final version to appear in Found. Comput. Math

Scientific paper

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 in the complexity theory over the reals (in the sense of Blum-Shub-Smale real machines) has been missing so far. In this paper we formulate and prove a real analogue of Toda's theorem. Unlike Toda's proof in the discrete case, which relied on sophisticated combinatorial arguments, our proof is topological in nature. As a consequence of our techniques we are also able to relate the computational hardness of two extremely well-studied problems in algorithmic semi-algebraic geometry -- namely the problem of deciding sentences in the first order theory of the reals with a constant number of quantifier alternations, and that of computing Betti numbers of semi-algebraic sets. We obtain a polynomial time reduction of the compact version of the first problem to the second. This latter result might be of independent interest to researchers in algorithmic semi-algebraic geometry.

Affiliated with

Also associated with

No associations

Rating

Polynomial hierarchy, Betti numbers and a real analogue of Toda's theorem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Polynomial hierarchy, Betti numbers and a real analogue of Toda's theorem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polynomial hierarchy, Betti numbers and a real analogue of Toda's theorem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-366129