A circuit-based proof of Toda's theorem

DOI10.1006/inco.1993.1033zbMath0772.68041OpenAlexW1991410070MaRDI QIDQ2366565

V. Vinay, H. Venkateswaran, Ravindran Kannan, Andrew Chi-Chih Yao

Publication date: 30 August 1993

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1993.1033

zbMATH Keywords

polynomial hierarchyrandomized reductions

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

On ACC, Nonuniform ACC Circuit Lower Bounds, Uniform proofs of ACC representations, Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy, Non-commutative arithmetic circuits: depth reduction and size lower bounds, Derandomizing Isolation in Space-Bounded Settings