__
TR04-072 | 19th August 2004 00:00
__

#### Hausdorff Dimension and Oracle Constructions

**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 Phi, then the set of oracles relative to which

Phi 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 intersect coNP^A

relative to a Hausdorff dimension 1 set of oracles.