__
TR02-065 | 26th November 2002 00:00
__

#### Measure on P revisited

**Abstract:**
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

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.