PP is closed under truth-table reductions
From MaRDI portal
Publication:1908349
DOI10.1006/INCO.1996.0001zbMATH Open0851.68029OpenAlexW2043323794MaRDI QIDQ1908349FDOQ1908349
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
Cited In (23)
- Quantum computing, postselection, and probabilistic polynomial-time
- Title not available (Why is that?)
- Structural complexity of rational interactive proofs
- On pseudorandomness and resource-bounded measure
- Complexity limitations on one-turn quantum refereed games
- Query order in the polynomial hierarchy
- Generalized theorems on relationships among reducibility notions to certain complexity classes
- On sparse hard sets for counting classes
- When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
- The consequences of eliminating NP solutions
- Structural control in weighted voting games
- Relationships among $PL$, $\#L$, and the determinant
- Counting classes and the fine structure between \(\mathrm{NC}^1\) and \(L\)
- On closure properties of GapP
- Circuits over PP and PL
- Immunity and Simplicity for Exact Counting and Other Counting Classes
- A structured view on weighted counting with relations to counting, quantum computation and applications
- A complexity theory for feasible closure properties
- CNF and DNF succinct graph encodings
- A relationship between difference hierarchies and relativized polynomial hierarchies
- Some results on selectivity and self-reducibility
- Approximate set union via approximate randomization
- PP is closed under intersection
Recommendations
- PP is closed under intersection 👍 👎
- Partial truth table reducibility 👍 👎
- A Note on Bounded-Truth-Table Reducibility 👍 👎
- Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete 👍 👎
- On sets bounded truth-table reducible to $P$-selective sets 👍 👎
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- Quasi-linear truth-table reductions to \(p\)-selective sets 👍 👎
This page was built for publication: PP is closed under truth-table reductions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1908349)
