Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with resource bounded measure:
TR02-015 | 13th February 2002
Philippe Moser

ZPP is hard unless RP is small

Revisions: 1

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

TR02-065 | 26th November 2002
Olivier Powell

Measure on P revisited

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

TR03-028 | 28th February 2003
Olivier Powell

PSPACE contains almost complete problems

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

TR03-029 | 1st April 2003
Philippe Moser

BPP has effective dimension at most 1/2 unless BPP=EXP

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

ISSN 1433-8092 | Imprint