Structural properties of oracle classes

DOI10.1016/J.IPL.2009.07.009MaRDI QIDQ990941zbMATH OpenOpenAlexFDO

Authors S. Zivny

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)

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

Cites work

• scientific article; zbMATH DE number 3883611 (Why is no real title available?)
• scientific article; zbMATH DE number 46423 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 559220 (Why is no real title available?)
• Boolean operations, joins, and the extended low hierarchy
• Lower bounds for the low hierarchy
• On sparse oracles separating feasible complexity classes
• PP is as Hard as the Polynomial-Time Hierarchy
• 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
• Sparse Sets, Lowness and Highness
• The complexity theory companion
• The strong exponential hierarchy collapses

Cited in

(2)

• scientific article; zbMATH DE number 4074483 (Why is no real title available?)
• The complexity of valued CSPs

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)