Circuits over PP and PL
From MaRDI portal
Publication:1567408
DOI10.1006/jcss.1999.1676zbMath0956.68069MaRDI QIDQ1567408
Publication date: 12 March 2001
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/3326ba6877b38b33949caeb25698699793461418
68Q25: Analysis of algorithms and problem complexity
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Probabilistic polynomial time is closed under parity reductions
- Space-bounded hierarchies and probabilistic computations
- Relativized circuit complexity
- When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
- PP is closed under intersection
- PP is closed under truth-table reductions
- PP is as Hard as the Polynomial-Time Hierarchy
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- An Optimal Parallel Algorithm for Formula Evaluation
- Computational Complexity of Probabilistic Turing Machines
- NP trees and Carnap's modal logic
- The Parallel Evaluation of General Arithmetic Expressions