ECCC-Report TR02-065https://eccc.weizmann.ac.il/report/2002/065Comments and Revisions published for TR02-065en-usTue, 03 Dec 2002 20:02:02 +0200
Paper TR02-065
| Measure on P revisited |
Olivier Powell
https://eccc.weizmann.ac.il/report/2002/065We revisit the problem of generalising Lutz's resource bounded measure
(rbm) to small complexity classes.
We propose a definition of a perfect rbm on P,
and give sufficient and necessary conditions for such a measure to exist.
We also revisit $\mu_\tau$, an rbm for P
defined in previous articles (c.f. full abstract for references), and correct an erroneous claim concerning the relations between $\mu_\tau$ and random sets.
The interest of generalising Lutz's rbm to small complexity classes,
such as P, is that the theory of rbm has proven itself a useful
tool in understanding the structure of big complexity classes such as E
or EXP, and that small complexity classes are perhaps those of higher
interest.
Generalising rbm to small complexity classes has been studied in
different previous articles (c.f. full abstract for references)
for P. We merely revisit the measure on $\mu_\tau$ from a previous article, and besides correcting an erroneous claim concerning the relations between this rbm and random sets, construct a better rbm,
which we argue as being a perfect generalisation of Lutz's rbm to P,
but which we can only prove to exist under the hypothesis of the existence of random sets.
Tue, 03 Dec 2002 20:02:02 +0200https://eccc.weizmann.ac.il/report/2002/065