首页 | 本学科首页   官方微博 | 高级检索  
     


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 View the MathML source the class of oracles relative to which View the MathML source (collapsing oracles), and by View the MathML source the class of oracles relative to which View the MathML source (separating oracles). We present structural results on View the MathML source and View the MathML source. Using a diagonalization argument, we show that neither View the MathML source nor View the MathML source is closed under disjoint union, also known as join. We show that this implies that neither View the MathML source nor View the MathML source is closed under union, intersection, or symmetric difference. Consequently View the MathML source, the first level of the extended low hierarchy, is not closed under join.
Keywords:Computational complexity  Diagonalization  Extended hierarchies  Relativization
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号