### Stanislav Zivny

## Properties of oracle classes that collapse or separate complexity classes

Vrije Universiteit in Amsterdam, Department of Theoretical Computer Science

July 2005
**Abstract**

Denote X the class of sets relative to which P=NP relativized and Z the class of
sets relative to which P!=NP. Besides presenting known properties about X and Z,
we also show that complete problems for exponential complexity classes and
stronger ones belong to X. We show that some complete problems, if they ever
exist, for deterministic classes between polynomial and exponential time do not
belong to X. We show that hard problems for exponential classes do not generally
belong to X. We characterize sets in X as the sets in the intersection of the
first level of the extended low and the zeroth level of the extended high
hierarchy. Further, we prove that neither X nor Z is closed under unions,
intersections and symmetric differences. We also prove that Z is not closed
under disjoint unions which implies that disjoint union can lower complexity
measured in terms of extended lowness.

**Table of Contents**

1. Introduction
2. Preliminaries
3. Relativization
4. Collapsing Oracles
5. Separating Oracles
6. Conclusion

**Number of pages:** 73