Hausdorff dimension and oracle constructions

Bennett and Gill [Relative to a random oracle A, PA≠NPA≠co-NPA with probability 1, SIAM J. Comput. 10 (1981) 96–113] 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.