A complex analogue of Toda's theorem

DOI10.1007/s10208-011-9105-5zbMath1268.14016arXiv0912.2652OpenAlexW2963903452MaRDI QIDQ454132

Saugata Basu

Publication date: 1 October 2012

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

polynomial hierarchyBetti numbersconstructible setsPoincare polynomial

Mathematics Subject Classification ID

Classical real and complex (co)homology in algebraic geometry (14F25) Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Complexity classes and completeness in algebraic geometry ⋮ Connectivity of joins, cohomological quantifier elimination, and an algebraic Toda's theorem ⋮ 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
• Unnamed Item
• On a problem posed by Steve Smale
• NP is as easy as detecting unique solutions
• Real quantifier elimination is doubly exponential
• La conjecture de Weil. II
• The polynomial-time hierarchy
• Algebraic cycles and homotopy theory
• Probabilistic complexity classes and lowness
• 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\)?
• Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem
• On the complexity of deciding connectedness and computing Betti numbers of a complex algebraic variety
• Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
• Counting complexity classes for numeric computations. III: Complex projective sets
• Smale’s 17th problem: Average polynomial time to compute affine and projective solutions
• PP is as Hard as the Polynomial-Time Hierarchy
• Complexity of Bezout's Theorem I: Geometric Aspects
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• BETTI NUMBERS OF SEMIALGEBRAIC AND SUB-PFAFFIAN SETS
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• 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
• Sums of Betti numbers in arbitrary characteristic.