ECCC-Report TR03-046https://eccc.weizmann.ac.il/report/2003/046Comments and Revisions published for TR03-046en-usFri, 13 Jun 2003 19:31:20 +0300
Paper TR03-046
| Locally Computed Baire's Categories on Small Complexity Classes |
Philippe Moser
https://eccc.weizmann.ac.il/report/2003/046We 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.
Fri, 13 Jun 2003 19:31:20 +0300https://eccc.weizmann.ac.il/report/2003/046