Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR03-046 | 11th June 2003 00:00

Locally Computed Baire's Categories on Small Complexity Classes


Authors: Philippe Moser
Publication: 13th June 2003 19:31
Downloads: 3370


We strengthen an earlier notion of
resource-bounded Baire's categories, and define
resource bounded Baire's categories on small complexity classes such as P, QP, SUBEXP
and on probabilistic complexity classes such as BPP.
We give an alternative characterization of meager sets via resource-bounded
Banach Mazur games.
We show that the class SPARSE is meager in P.
We investigate the genericity notion arising from our categories,
and show that generic sets are REC-immune.
We show that there is no weak-completeness notion based on our categories,
i.e. every weakly-complete set is complete. Next we prove that the class
of complete sets for P under Turing-logspace reductions is meager in P
if P is not equal to DSPACE(log n), and that the same holds unconditionally
for QP.
Finally we show the following for our resource-bounded Baire's category on SUBEXP.
First BPP is meager unless BPP equals EXP infinitely often.
Second NP equals AM infinitely often unless NP is meager,
and finally either RP is meager or ZPP equals RP infinitely often.

ISSN 1433-8092 | Imprint