ECCC-Report TR04-072https://eccc.weizmann.ac.il/report/2004/072Comments and Revisions published for TR04-072en-usThu, 19 Aug 2004 09:47:46 +0300
Paper TR04-072
| Hausdorff Dimension and Oracle Constructions |
John Hitchcock
https://eccc.weizmann.ac.il/report/2004/072 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.
Thu, 19 Aug 2004 09:47:46 +0300https://eccc.weizmann.ac.il/report/2004/072