A complex analogue of Toda's theorem
type: Item
instance of: scholarly article
title: A complex analogue of Toda's theorem
zbMATH Open document ID: 1268.14016
author: Saugata Basu
published in: Foundations of Computational Mathematics
publication date: 2012-10-01T00:00:00Z
full work available at URL: https://arxiv.org/abs/0912.2652
review text: \textit{S. Toda}'s, theorem [SIAM J. Comput. 20, No. 5, 865--877 (1991; Zbl 0733.68034)] states that the discrete polynomial time hierarchy is contained in the class of languages of polynomial time with respect to an oracle computing a function in \(\#P\). A real analogue has been given by the author and \textit{T. Zell} [Found. Comput. Math. 10, No. 4, 429--454 (2010; Zbl 1200.14108)]. This paper contains a complex analogue.
reviewed by: Josef Schicho
Mathematics Subject Classification ID: 14F25
Mathematics Subject Classification ID: 14Q20
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 6088728
zbMATH Keywords: polynomial hierarchy
zbMATH Keywords: Betti numbers
zbMATH Keywords: Poincare polynomial
zbMATH Keywords: constructible sets
MaRDI profile type: Publication
OpenAlex ID: W2963903452
arXiv ID: 0912.2652
cites work: Q5460918
cites work: Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem
cites work: Smale’s 17th problem: Average polynomial time to compute affine and projective solutions
cites work: On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
cites work: COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
cites work: Q5465357
cites work: Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
cites work: On a problem posed by Steve Smale
cites work: Counting complexity classes for numeric computations. III: Complex projective sets
cites work: Real quantifier elimination is doubly exponential
cites work: La conjecture de Weil. I
cites work: La conjecture de Weil. II
cites work: On the Rationality of the Zeta Function of an Algebraic Variety
cites work: BETTI NUMBERS OF SEMIALGEBRAIC AND SUB-PFAFFIAN SETS
cites work: Q3247612
cites work: Sums of Betti numbers in arbitrary characteristic.
cites work: Algebraic cycles and homotopy theory
cites work: 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
cites work: Q4528987
cites work: Counting problems over the reals
cites work: Q4298260
cites work: On the complexity of deciding connectedness and computing Betti numbers of a complex algebraic variety
cites work: Probabilistic complexity classes and lowness
cites work: Complexity of Bezout's Theorem I: Geometric Aspects
cites work: On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?''
cites work: The polynomial-time hierarchy
cites work: PP is as Hard as the Polynomial-Time Hierarchy
cites work: NP is as easy as detecting unique solutions
cites work: Numbers of solutions of equations in finite fields
DOI: 10.1007/S10208-011-9105-5
description: scientific article; zbMATH DE number 6088728