Philippe Moser

We use Lutz's resource bounded measure theory to prove that either \tbf{RP} is

small or \tbf{ZPP} is hard. More precisely we prove that if \tbf{RP} has not p-measure zero, then \tbf{EXP} is contained

in $\mbf{ZPP}/n$.

We also show that if \tbf{RP} has not p-measure zero,

\tbf{EXP} equals ...
more >>>

Olivier Powell

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

Olivier Powell

An almost complete set A for a complexity class C is a language of C which is not complete, but that has the property that ``many'' languages of C reduce to A, where the term ``many'' is used in reference to Lutz's resource bounded measure (rbm). The question of the ... more >>>

Philippe Moser

We prove that BPP has Lutz's p-dimension at most 1/2 unless BPP equals EXP.

Next we show that BPP has Lutz's p-dimension zero unless BPP equals EXP

on infinitely many input lengths.

We also prove that BPP has measure zero in the smaller complexity

class ...
more >>>