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

DOI10.1007/s10208-010-9062-4zbMath1200.14108arXiv0812.1200OpenAlexW2136302685MaRDI QIDQ1959088

Saugata Basu, Thierry Zell

Publication date: 6 October 2010

Published in: Foundations of Computational Mathematics, 2009 50th Annual IEEE Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0812.1200

zbMATH Keywords

polynomial hierarchyBetti numberssemi-algebraic setsToda's theorem

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Semialgebraic sets and related spaces (14P10) Topology of real algebraic varieties (14P25)

Related Items

Some Results on Interactive Proofs for Real Computations, A complex analogue of Toda's theorem, On homotopy types of limits of semi-algebraic sets and additive complexity of polynomials, CATEGORICAL COMPLEXITY, Complexity classes and completeness in algebraic geometry, Connectivity of joins, cohomological quantifier elimination, and an algebraic Toda's theorem, Interactive proofs and a Shamir-like result for real number computations, Vandermonde varieties, mirrored spaces, and the cohomology of symmetric semi-algebraic sets, A complexity theory of constructible functions and sheaves, A Survey on Analog Models of Computation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Constructible motivic functions and motivic integration
• Computing the first Betti number of a semi-algebraic set
• Locally semialgebraic spaces
• NP is as easy as detecting unique solutions
• Solving systems of polynomial inequalities in subexponential time
• La conjecture de Weil. II
• On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
• Counting connected components of a semialgebraic set in subexponential time
• The polynomial-time hierarchy
• Probabilistic complexity classes and lowness
• Complexity of deciding Tarski algebra
• On bounding the Betti numbers and computing the Euler characteristic of semi-algebraic sets
• Construction of roadmaps in semi-algebraic sets
• Counting problems over the reals
• La conjecture de Weil. I
• On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?
• Computing the first few Betti numbers of semi-algebraic sets in single exponential time
• Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
• Counting complexity classes for numeric computations. III: Complex projective sets
• Computing Roadmaps of General Semi-Algebraic Sets
• PP is as Hard as the Polynomial-Time Hierarchy
• Algorithmic Semi-algebraic Geometry and Topology -- Recent Progress and Open Problems
• O-MINIMAL CECH COHOMOLOGY
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• On the combinatorial and algebraic complexity of quantifier elimination
• BETTI NUMBERS OF SEMIALGEBRAIC AND SUB-PFAFFIAN SETS
• Poset fiber theorems
• Computing roadmaps of semi-algebraic sets on a variety
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Approximation of definable sets by compact families, and upper bounds on homotopy and homology
• On the Rationality of the Zeta Function of an Algebraic Variety
• Numbers of solutions of equations in finite fields
• Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler