Abstract:
Bennett and Gill (1981) proved that P^{A} ≠ NP^{A} relative to a
random oracle A, or in other words, that the set

O_{[P=NP]} = { A | P^{A} = NP^{A }}

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 P^{A} ≠ NP^{A}
∩ coNP^{A} relative to a Hausdorff dimension 1 set of
oracles.