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