Polynomial Hierarchy, Betti Numbers, and a Real Analogue of Toda’s Theorem
Polynomial Hierarchy, Betti Numbers, and a Real Analogue of Toda’s Theorem
复制标题
多项式层次、贝蒂数和户田定理的实类比
DOI：
10.1007/s10208-010-9062-4
复制
发表时间：
2008
影响因子：
3
通讯作者：
T. Zell
中科院分区：
文献类型：
--
作者：
S. Basu;T. Zell
Toda （inSIAM J. computer . 20(5): 865-877, 1991）在1989年证明了（离散的）多项式时间层次PH包含在类p# P中，即在给定具有计算复杂度类#P中计算函数的能力的oracle的情况下，图灵机可以在多项式时间内决定的语言类。这个结果，说明了计数的力量，被认为是计算复杂性理论的一个开创性的结果。在关于实数的复杂性理论中有一个类似的结果（在布卢姆-舒伯-小实数机器的意义上）。点。数学。Soc。（科学通报）21(1):1 - 46,1989)至今仍未找到。本文给出并证明了Toda定理的一个真实的类比。不像Toda在离散情况下的证明依赖于复杂的组合论证，我们的证明本质上是拓扑的。由于我们的技术，我们还能够将算法半代数几何中两个研究得非常充分的问题的计算难度联系起来：在一阶实数理论中确定具有常数数量量词交替的句子的问题，以及计算半代数集的Betti数的问题。我们得到了第一个问题的压缩版本到第二个问题的多项式时间化简。后一种结果可能会引起算法半代数几何研究人员的独立兴趣。
Toda (inSIAM J. Comput. 20(5):865–877, 1991) proved in 1989 that the (discrete) polynomial time hierarchy,PH, is contained in the classP#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 #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 inBull. Am. Math. Soc. (NS)21(1): 1–46, 1989) 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: 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 may be of independent interest to researchers in algorithmic semi-algebraic geometry.