An oracle separating \(\oplus P\) from \(PP^{PH}\)

DOI10.1016/0020-0190(91)90035-GzbMath0714.68032MaRDI QIDQ751272

Frederic Green

Publication date: 1991

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

zbMATH Keywords

computational complexitypolynomial-time hierarchyprobabilistic polynomial timerelativized complexity classthreshld circuits

Mathematics Subject Classification ID

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

Related Items (7)

Immunity and Simplicity for Exact Counting and Other Counting Classes ⋮ Upper and lower bounds for some depth-3 circuit classes ⋮ A lower bound for monotone perceptrons ⋮ On the correlation of symmetric functions ⋮ 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

Cites Work

• The complexity of combinatorial problems with succinct input representation
• Parallel computation with threshold functions
• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
• Relativized counting classes: Relations among thresholds, parity, and mods
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1

This page was built for publication: An oracle separating \(\oplus P\) from \(PP^{PH}\)