__
TR03-046 | 11th June 2003 00:00
__

#### Locally Computed Baire's Categories on Small Complexity Classes

**Abstract:**
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.