A complex analogue of Toda's theorem (Q454132): Difference between revisions

\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.

0 references

reviewed by

Josef Schicho

0 references

zbMATH Keywords

polynomial hierarchy

0 references

Betti numbers

0 references

Poincare polynomial

0 references

constructible sets

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Q5460918

0 references

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

0 references

Smale’s 17th problem: Average polynomial time to compute affine and projective solutions

0 references

On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines

0 references

COMPLEXITY AND REAL COMPUTATION: A MANIFESTO

0 references

Q5465357

0 references

Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets

0 references

On a problem posed by Steve Smale

0 references

Counting complexity classes for numeric computations. III: Complex projective sets

0 references

Real quantifier elimination is doubly exponential

0 references

La conjecture de Weil. I

0 references

La conjecture de Weil. II

0 references

On the Rationality of the Zeta Function of an Algebraic Variety

0 references

BETTI NUMBERS OF SEMIALGEBRAIC AND SUB-PFAFFIAN SETS

0 references

Q3247612

0 references

Sums of Betti numbers in arbitrary characteristic.

0 references

Algebraic cycles and homotopy theory

0 references

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

0 references

Q4528987

0 references

Counting problems over the reals

0 references

Q4298260

0 references

On the complexity of deciding connectedness and computing Betti numbers of a complex algebraic variety

0 references

Probabilistic complexity classes and lowness

0 references

Complexity of Bezout's Theorem I: Geometric Aspects

0 references

On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?''

0 references

The polynomial-time hierarchy

0 references

PP is as Hard as the Polynomial-Time Hierarchy

0 references

NP is as easy as detecting unique solutions

0 references

Numbers of solutions of equations in finite fields

0 references

Identifiers

zbMATH Open document ID

1268.14016

0 references

DOI

10.1007/s10208-011-9105-5

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:454132

@@ Property / 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.
+Normal rank
@@ Property / reviewed by @@
+Josef Schicho
@@ Property / reviewed by: Josef Schicho / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+F25
@@ Property / Mathematics Subject Classification ID: 14F25 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+Q20
@@ Property / Mathematics Subject Classification ID: 14Q20 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+Q15
@@ Property / Mathematics Subject Classification ID: 68Q15 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+6088728
@@ Property / zbMATH DE Number: 6088728 / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+polynomial hierarchy
@@ Property / zbMATH Keywords: polynomial hierarchy / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+Betti numbers
@@ Property / zbMATH Keywords: Betti numbers / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+Poincare polynomial
@@ Property / zbMATH Keywords: Poincare polynomial / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+constructible sets
@@ Property / zbMATH Keywords: constructible sets / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2963903452
@@ Property / OpenAlex ID: W2963903452 / rank @@
+Normal rank
@@ Property / arXiv ID @@
+.2652
@@ Property / arXiv ID: 0912.2652 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5460918
@@ Property / cites work: Q5460918 / rank @@
+Normal rank
@@ Property / cites work @@
+Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem
+Normal rank
@@ Property / cites work @@
+Smale’s 17th problem: Average polynomial time to compute affine and projective solutions
+Normal rank
@@ Property / cites work @@
+On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
+Normal rank
@@ Property / cites work @@
+COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
@@ Property / cites work: COMPLEXITY AND REAL COMPUTATION: A MANIFESTO / rank @@
+Normal rank
@@ Property / cites work @@
+Q5465357
@@ Property / cites work: Q5465357 / rank @@
+Normal rank
@@ Property / cites work @@
+Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
+Normal rank
@@ Property / cites work @@
+On a problem posed by Steve Smale
@@ Property / cites work: On a problem posed by Steve Smale / rank @@
+Normal rank
@@ Property / cites work @@
+Counting complexity classes for numeric computations. III: Complex projective sets
+Normal rank
@@ Property / cites work @@
+Real quantifier elimination is doubly exponential
@@ Property / cites work: Real quantifier elimination is doubly exponential / rank @@
+Normal rank
@@ Property / cites work @@
+La conjecture de Weil. I
@@ Property / cites work: La conjecture de Weil. I / rank @@
+Normal rank
@@ Property / cites work @@
+La conjecture de Weil. II
@@ Property / cites work: La conjecture de Weil. II / rank @@
+Normal rank
@@ Property / cites work @@
+On the Rationality of the Zeta Function of an Algebraic Variety
+Normal rank
@@ Property / cites work @@
+BETTI NUMBERS OF SEMIALGEBRAIC AND SUB-PFAFFIAN SETS
+Normal rank
@@ Property / cites work @@
+Q3247612
@@ Property / cites work: Q3247612 / rank @@
+Normal rank
@@ Property / cites work @@
+Sums of Betti numbers in arbitrary characteristic.
+Normal rank
@@ Property / cites work @@
+Algebraic cycles and homotopy theory
@@ Property / cites work: Algebraic cycles and homotopy theory / rank @@
+Normal rank
@@ Property / 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
+Normal rank
@@ Property / cites work @@
+Q4528987
@@ Property / cites work: Q4528987 / rank @@
+Normal rank
@@ Property / cites work @@
+Counting problems over the reals
@@ Property / cites work: Counting problems over the reals / rank @@
+Normal rank
@@ Property / cites work @@
+Q4298260
@@ Property / cites work: Q4298260 / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of deciding connectedness and computing Betti numbers of a complex algebraic variety
+Normal rank
@@ Property / cites work @@
+Probabilistic complexity classes and lowness
@@ Property / cites work: Probabilistic complexity classes and lowness / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity of Bezout's Theorem I: Geometric Aspects
+Normal rank
@@ Property / cites work @@
+On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?''
+Normal rank
@@ Property / cites work @@
+The polynomial-time hierarchy
@@ Property / cites work: The polynomial-time hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+PP is as Hard as the Polynomial-Time Hierarchy
@@ Property / cites work: PP is as Hard as the Polynomial-Time Hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+NP is as easy as detecting unique solutions
@@ Property / cites work: NP is as easy as detecting unique solutions / rank @@
+Normal rank
@@ Property / cites work @@
+Numbers of solutions of equations in finite fields
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:454132