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

ACO Seminar
Friday, April 10, 2009 - 3:00pm for 1 hour (actually 50 minutes)
Skiles 255
Saugata Basu – School of Mathematics, Georgia Tech and Purdue University
Prasad Tetali
Toda proved in 1989 that the (discrete) polynomial time hierarchy, {\bf PH}, is contained in the class {\bf P}^{#\bf 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 #{\bf 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 Turing machines) has been missing so far. 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. (Joint work with Thierry Zell.)