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