PP is closed under truth-table reductions
From MaRDI portal
Publication:1908349
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
Related Items
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
