Baire categories on small complexity classes and meager-comeager laws
From MaRDI portal
Publication:2475805
DOI10.1016/j.ic.2007.10.002zbMath1133.68022MaRDI QIDQ2475805
Publication date: 11 March 2008
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2007.10.002
54E52: Baire category, Baire spaces
60C05: Combinatorial probability
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Martingale families and dimension in P, Resource-bounded measure on probabilistic classes, A zero-one law for RP and derandomization of AM if NP is not small, Generic density and small span theorem
Cites Work
- The size of SPP
- Almost everywhere high nonuniform complexity
- Measure on \(P\): Strength of the notion
- The zero-one law holds for BPP
- Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
- Category and Measure in Complexity Classes
- Weakly Hard Problems
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item