The zero-one law holds for BPP

DOI10.1016/S0304-3975(00)00191-2zbMath0945.68057MaRDI QIDQ1575726

Dieter van Melkebeek

Publication date: 21 August 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

computational complexityderandomizationtheory of computationzero-one lawresource-bounded measure

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

A zero-one law for RP and derandomization of AM if NP is not small ⋮ The size of SPP ⋮ A zero-one SUBEXP-dimension law for BPP ⋮ Martingale families and dimension in P ⋮ Upward separations and weaker hypotheses in resource-bounded measure ⋮ Baire categories on small complexity classes and meager-comeager laws

Cites Work

• Almost everywhere high nonuniform complexity
• Measure, Stochasticity, and the Density of Hard Languages
• Results on resource-bounded measure
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item