Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem
From MaRDI portal
DOI10.1109/FOCS.2009.70zbMath1200.14108arXiv0812.1200OpenAlexW2136302685MaRDI QIDQ1959088
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
Symbolic computation and algebraic computation (68W30) Semialgebraic sets and related spaces (14P10) Topology of real algebraic varieties (14P25)
Related Items (11)
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 ⋮ Beyond the Existential Theory of the Reals ⋮ 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
This page was built for publication: Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem
