An oracle separating P from PP^PH

DOI10.1016/0020-0190(91)90035-GzbMATH Open0714.68032MaRDI QIDQ751272FDOQ751272

Authors: Frederic Green 

Publication date: 1991

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityprobabilistic polynomial timepolynomial-time hierarchyrelativized complexity classthreshld circuits

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Cites Work

• The complexity of combinatorial problems with succinct input representation
• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
• 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

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)