A zero-one SUBEXP-dimension law for BPP
From MaRDI portal
Publication:1944915
DOI10.1016/j.ipl.2011.01.019zbMath1260.68148OpenAlexW2014038409MaRDI 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 complexityderandomizationcomplexity theoryresource-bounded measureresource-bounded dimension
Data structures (68P05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
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
This page was built for publication: A zero-one SUBEXP-dimension law for BPP
