Hausdorff Reductions and the Exponential Hierarchies
For complexity theorists, it offers a unified structural framework for understanding oracle-based hierarchy levels and collapses, and provides new complete problems for previously open classes.
The paper introduces Hausdorff complexity classes to provide oracle-free characterizations of intermediate levels of exponential hierarchies, resolving a question of Hemachandra by showing that P^{NExp} = NP^{NExp} because both equal the same Hausdorff class, and defines canonical complete problems for P^{NExp[Log]} with matching lower bounds.
We introduce Hausdorff (complexity) classes, which provide canonical characterizations of the intermediate levels of the iterated exponential hierarchies, including the Polynomial Hierarchy, the (Weak) Exponential Hierarchy, and higher-order exponential hierarchies. As certificates characterize main hierarchy levels without oracles, Hausdorff classes give an oracle-free characterization of intermediate hierarchy levels. The Hausdorff perspective provides a structural explanation for many known equivalences between oracle classes. In particular, seemingly different oracle classes corresponding to the same intermediate level are shown to arise from just three different, yet equivalent, oracle-aided approaches to deciding languages in a single Hausdorff class, thus replacing multiple oracle-based views with a unique characterization. It also explains the collapse of the Strong Exponential Hierarchy, showing that $\mathrm{P}^{\mathrm{NExp}} = \mathrm{NP}^{\mathrm{NExp}}$ arises because both classes coincide with the same Hausdorff class, thereby resolving a question of Hemachandra. Finally, we define canonical complete problems yielding matching lower bounds for $\mathrm{P}^{\mathrm{NExp[Log]}}$ problems whose hardness was left open due to the lack of known $\mathrm{P}^{\mathrm{NExp[Log]}}$-complete problems.