PP is closed under truth-table reductions

DOI10.1006/INCO.1996.0001zbMath0851.68029OpenAlexW2043323794MaRDI QIDQ1908349

Nick Reingold, Lance J. Fortnow

Publication date: 27 March 1996

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

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

zbMATH Keywords

probabilistic computation

Mathematics Subject Classification ID

Theory of software (68N99)

Related Items (22)

A complexity theory for feasible closure properties ⋮ On closure properties of GapP ⋮ A relationship between difference hierarchies and relativized polynomial hierarchies ⋮ Immunity and Simplicity for Exact Counting and Other Counting Classes ⋮ When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one ⋮ Query order in the polynomial hierarchy ⋮ Generalized theorems on relationships among reducibility notions to certain complexity classes ⋮ Complexity limitations on one-turn quantum refereed games ⋮ Structural complexity of rational interactive proofs ⋮ A structured view on weighted counting with relations to counting, quantum computation and applications ⋮ The consequences of eliminating NP solutions ⋮ Relationships among $PL$, $\#L$, and the determinant ⋮ Some results on selectivity and self-reducibility ⋮ CNF and DNF succinct graph encodings ⋮ On sparse hard sets for counting classes ⋮ Quantum computing, postselection, and probabilistic polynomial-time ⋮ On pseudorandomness and resource-bounded measure ⋮ Unnamed Item ⋮ Approximate set union via approximate randomization ⋮ Counting classes and the fine structure between \(\mathrm{NC}^1\) and \(L\) ⋮ Circuits over PP and PL ⋮ Structural control in weighted voting games

This page was built for publication: PP is closed under truth-table reductions