Probabilistic polynomial time is closed under parity reductions
From MaRDI portal
Cites work
- Bounded queries to SAT and the Boolean hierarchy
- Computational Complexity of Probabilistic Turing Machines
- scientific article; zbMATH DE number 3917710 (Why is no real title available?)
- scientific article; zbMATH DE number 4041255 (Why is no real title available?)
- On the power of parity polynomial time
- The complexity of combinatorial problems with succinct input representation
- The complexity of facets (and some facets of complexity)
- The complexity of optimization problems
- The difference and truth-table hierarchies for NP
- The strong exponential hierarchy collapses
Cited in
(14)- Probabilistic weak simulation is decidable in polynomial time
- With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
- On sparse hard sets for counting classes
- Graph isomorphism is low for PP
- A lower bound for perceptrons and an oracle separation of the \(PP^{PH}\) hierarchy
- Perceptrons, PP, and the polynomial hierarchy
- Circuits over PP and PL
- Probabilistic parameterized polynomial time
- A complexity theory for feasible closure properties
- Simultaneous strong separations of probabilistic and unambiguous complexity classes
- Manipulating the quota in weighted voting games
- Generalized theorems on relationships among reducibility notions to certain complexity classes
- Kolmogorov characterizations of complexity classes
- On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P
This page was built for publication: Probabilistic polynomial time is closed under parity reductions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q751270)
