Structural properties of oracle classes

DOI10.1016/J.IPL.2009.07.009zbMath1206.68134OpenAlexW2010318155MaRDI QIDQ990941

Stanislav Živný

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

zbMATH Keywords

computational complexitydiagonalizationrelativizationextended hierarchies

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

The Complexity of Valued CSPs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The strong exponential hierarchy collapses
• On sparse oracles separating feasible complexity classes
• Boolean operations, joins, and the extended low hierarchy
• PP is as Hard as the Polynomial-Time Hierarchy
• Sparse Sets, Lowness and Highness
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Lower bounds for the low hierarchy
• The complexity theory companion

This page was built for publication: Structural properties of oracle classes