A note on the circuit complexity of PP

DOI10.1016/j.tcs.2005.07.032zbMath1080.68041OpenAlexW2151586869MaRDI QIDQ2576885

N. V. Vinodchandran

Publication date: 29 December 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.07.032

zbMATH Keywords

computational complexitycomplexity classescircuit lower bounds

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (5)

Robust simulations and significant separations ⋮ Unnamed Item ⋮ On Pseudodeterministic Approximation Algorithms. ⋮ Relations and equivalences between circuit lower bounds and karp-lipton theorems ⋮ Quantum generalizations of the polynomial hierarchy with applications to \(\mathrm{QMA(2)}\)

Cites Work

• Unnamed Item
• Unnamed Item
• If NP has polynomial-size circuits, then MA=AM
• Arithmetization: A new method in structural complexity theory
• Relativized circuit complexity
• Probabilistic complexity classes and lowness
• Perceptrons, PP, and the polynomial hierarchy
• Circuit-size lower bounds and non-reducibility to sparse sets
• Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
• Computational Complexity of Probabilistic Turing Machines
• Algebraic methods for interactive proof systems

This page was built for publication: A note on the circuit complexity of PP