Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR02-065 | 26th November 2002 00:00

Measure on P revisited


Authors: Olivier Powell
Publication: 3rd December 2002 20:02
Downloads: 1099


We 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
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.

ISSN 1433-8092 | Imprint