Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Olivier Powell:

TR05-010 | 8th December 2004
Olivier Powell

Almost Completeness in Small Complexity Classes

We constructively prove the existence of almost complete problems under logspace manyone reduction for some small complexity classes by exhibiting a parametrizable construction which yields, when appropriately setting the parameters, an almost complete problem for PSPACE, the class of space efficiently decidable problems, and for SUBEXP, the class of problems ... 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 >>>

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

ISSN 1433-8092 | Imprint