scientific article; zbMATH DE number 3988707
From MaRDI portal
Publication:3751005
[For the entire collection see Zbl 0591.00015.] In the present paper an overview is presented of diagonalisation methods which have been used for the construction of oracle sets relative to which complexity classes in the P-Time Hierarchy are separated structurally. A comparison of the methods is made on the basis of inherent properties. A characterisation of these properties leads to a first attempt for a taxonomy for these diagonalisation methods.
Recommendations
- scientific article; zbMATH DE number 4121422
- scientific article; zbMATH DE number 1860655
- Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets
- Diagonalizations over polynomial time computable sets
- scientific article; zbMATH DE number 1507040
Cited in
(11)- Simplicity, immunity, relativizations and nondeterminism
- Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets
- A uniform approach to define complexity classes
- A note on separating the relativized polynomial time hierarchy by immune sets
- A time-space hierarchy between polynomial time and polynomial space
- scientific article; zbMATH DE number 1507040 (Why is no real title available?)
- On the cutting edge of relativization: the resource bounded injury method
- scientific article; zbMATH DE number 4121422 (Why is no real title available?)
- scientific article; zbMATH DE number 1860655 (Why is no real title available?)
- scientific article; zbMATH DE number 817509 (Why is no real title available?)
- Strong self-reducibility precludes strong immunity
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3751005)