A complex analogue of Toda's theorem (Q454132): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
| 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. | |||
| 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. / rank | |||
Normal rank | |||
| Property / reviewed by | |||
| Property / reviewed by: Josef Schicho / rank | |||
Normal rank | |||
| Property / Mathematics Subject Classification ID | |||
| Property / Mathematics Subject Classification ID: 14F25 / rank | |||
Normal rank | |||
| Property / Mathematics Subject Classification ID | |||
| Property / Mathematics Subject Classification ID: 14Q20 / rank | |||
Normal rank | |||
| Property / Mathematics Subject Classification ID | |||
| Property / Mathematics Subject Classification ID: 68Q15 / rank | |||
Normal rank | |||
| Property / zbMATH DE Number | |||
| 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 | |||
Revision as of 11:10, 30 June 2023
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A complex analogue of Toda's theorem |
scientific article |
Statements
A complex analogue of Toda's theorem (English)
0 references
1 October 2012
0 references
\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
polynomial hierarchy
0 references
Betti numbers
0 references
Poincare polynomial
0 references
constructible sets
0 references
