Structural properties of oracle classes |
| |
Authors: | Stanislav
ivný |
| |
Affiliation: | aComputing Laboratory, University of Oxford, Wolfson Building, Parks Road, Oxford, OX1 3QD, UK |
| |
Abstract: | Denote by the class of oracles relative to which (collapsing oracles), and by the class of oracles relative to which (separating oracles). We present structural results on and . Using a diagonalization argument, we show that neither nor is closed under disjoint union, also known as join. We show that this implies that neither nor is closed under union, intersection, or symmetric difference. Consequently , the first level of the extended low hierarchy, is not closed under join. |
| |
Keywords: | Computational complexity Diagonalization Extended hierarchies Relativization |
本文献已被 ScienceDirect 等数据库收录! |
|