An oracle separating P from PP^PH
From MaRDI portal
Publication:751272
Recommendations
- Parity, circuits, and the polynomial-time hierarchy
- A lower bound for perceptrons and an oracle separation of the \(PP^{PH}\) hierarchy
- A general method to construct oracles realizing given relationships between complexity classes
- Random oracles separate PSPACE from the polynomial-time hierarchy
- Lower bounds for constant-depth circuits in the presence of help bits
Cites work
- Parallel computation with threshold functions
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Relativized counting classes: Relations among thresholds, parity, and mods
- The complexity of combinatorial problems with succinct input representation
- With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
Cited in
(9)- Perceptrons, PP, and the polynomial hierarchy
- On the correlation of symmetric functions
- A lower bound for perceptrons and an oracle separation of the \(PP^{PH}\) hierarchy
- Relating polynomial time to constant depth
- On the correlation of symmetric functions
- Upper and lower bounds for some depth-3 circuit classes
- Random oracles separate PSPACE from the polynomial-time hierarchy
- Immunity and Simplicity for Exact Counting and Other Counting Classes
- A lower bound for monotone perceptrons
This page was built for publication: An oracle separating \(\oplus P\) from \(PP^{PH}\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q751272)
