A new characterization of \(\text{ACC}^{0}\) and probabilistic \(\text{CC}^{0}\)
From MaRDI portal
Publication:626674
DOI10.1007/s00037-010-0287-zzbMath1213.68262OpenAlexW2141836042MaRDI QIDQ626674
Kristoffer Arnsfelt Hansen, Michal Koucký
Publication date: 18 February 2011
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-010-0287-z
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items