Structural properties of oracle classes
From MaRDI portal
Publication:990941
DOI10.1016/J.IPL.2009.07.009zbMATH Open1206.68134OpenAlexW2010318155MaRDI QIDQ990941FDOQ990941
Publication date: 1 September 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ipl.2009.07.009
Recommendations
- scientific article; zbMATH DE number 4011940
- Oracles and relativizations of the P =? NP question for several structures
- A general method to construct oracles realizing given relationships between complexity classes
- On relativizations of the P =? NP question for several structures
- scientific article; zbMATH DE number 3871339
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- PP is as Hard as the Polynomial-Time Hierarchy
- The strong exponential hierarchy collapses
- The complexity theory companion
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- On sparse oracles separating feasible complexity classes
- Title not available (Why is that?)
- Boolean operations, joins, and the extended low hierarchy
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Title not available (Why is that?)
- Sparse Sets, Lowness and Highness
- Lower bounds for the low hierarchy
Cited In (2)
This page was built for publication: Structural properties of oracle classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q990941)
