Hausdorff Dimension and Oracle Constructions

John M. Hitchcock

Abstract:
Bennett and Gill (1981) proved that PA ≠ NPA relative to a random oracle A, or in other words, that the set

O[P=NP] = { A | PA = NPA }

has Lebesgue measure 0. In contrast, we show that O[P=NP] has Hausdorff dimension 1.

This follows from a much more general theorem: if there is a relativizable and paddable oracle construction for a complexity-theoretic statement Φ, then the set of oracles relative to which Φ holds has Hausdorff dimension 1.

We give several other applications including proofs that the polynomial-time hierarchy is infinite relative to a Hausdorff dimension 1 set of oracles and that PA ≠ NPA ∩ coNPA relative to a Hausdorff dimension 1 set of oracles.