Circuits over PP and PL
type: Item
instance of: scholarly article
title: Circuits over PP and PL
zbMATH Open document ID: 0956.68069
author: Richard Beigel
author: Bin Fu
published in: Journal of Computer and System Sciences
publication date: 2001-03-12T00:00:00Z
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1455742
zbMATH Keywords: oracle gates
zbMATH Keywords: Boolean formula reductions
zbMATH Keywords: BF reductions
MaRDI profile type: Publication
OpenAlex ID: W2106472514
cites work: When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
cites work: Probabilistic polynomial time is closed under parity reductions
cites work: PP is closed under intersection
cites work: Parallel computation for well-endowed rings and space-bounded probabilistic machines
cites work: The Parallel Evaluation of General Arithmetic Expressions
cites work: Q3140633
cites work: An Optimal Parallel Algorithm for Formula Evaluation
cites work: PP is closed under truth-table reductions
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: NP trees and Carnap's modal logic
cites work: Q3735080
cites work: Q5180413
cites work: Q4228457
cites work: Space-bounded hierarchies and probabilistic computations
cites work: PP is as Hard as the Polynomial-Time Hierarchy
cites work: Relativized circuit complexity
DOI: 10.1006/JCSS.1999.1676
description: scientific article; zbMATH DE number 1455742