Circuits over PP and PL

DOI10.1006/jcss.1999.1676zbMath0956.68069OpenAlexW2106472514MaRDI QIDQ1567408

Richard Beigel, Bin Fu

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

zbMATH Keywords

BF reductionsBoolean formula reductionsoracle gates

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (2)

Parameterised counting in logspace ⋮ Isolation, matching, and counting uniform and nonuniform upper bounds

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

This page was built for publication: Circuits over PP and PL