Structural properties of oracle classes (Q990941)

From MaRDI portal

Jump to:navigation, search

scientific article

Language	Label	Description	Also known as
English	Structural properties of oracle classes	scientific article

Statements

scholarly article

0 references

Structural properties of oracle classes (English)

0 references

Stanislav Živný

0 references

Information Processing Letters

0 references

publication date

1 September 2010

0 references

zbMATH Keywords

computational complexity

0 references

diagonalization

0 references

extended hierarchies

0 references

relativization

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1016/j.ipl.2009.07.009

0 references

Lower bounds for the low hierarchy

0 references

Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question

0 references

0 references

Sparse Sets, Lowness and Highness

0 references

0 references

0 references

Relative to a Random Oracle<i>A</i>, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1

0 references

0 references

On sparse oracles separating feasible complexity classes

0 references

The strong exponential hierarchy collapses

0 references

Boolean operations, joins, and the extended low hierarchy

0 references

The complexity theory companion

0 references

PP is as Hard as the Polynomial-Time Hierarchy

0 references

Identifiers

zbMATH Open document ID

0 references

10.1016/j.ipl.2009.07.009

0 references

Mathematics Subject Classification ID

0 references

0 references

zbMATH DE Number

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:990941

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q990941&oldid=35185161"