A zero-one SUBEXP-dimension law for BPP
From MaRDI portal
Publication:1944915
DOI10.1016/j.ipl.2011.01.019zbMath1260.68148MaRDI QIDQ1944915
Publication date: 28 March 2013
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: http://eprints.maynoothuniversity.ie/3838/1/PM_Zero-one.pdf
computational complexity; derandomization; complexity theory; resource-bounded measure; resource-bounded dimension
68P05: Data structures
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
Cites Work
- Martingale families and dimension in P
- Almost everywhere high nonuniform complexity
- Almost every set in exponential time is P-bi-immune
- Measure on \(P\): Strength of the notion
- The zero-one law holds for BPP
- Randomness vs time: Derandomization under a uniform assumption
- A zero-one law for RP and derandomization of AM if NP is not small
- Dimension in Complexity Classes