A new characterization of \(\text{ACC}^{0}\) and probabilistic \(\text{CC}^{0}\)

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

zbMATH Keywords

planaritybranching programsBoolean circuitsAND functionmodular countingprobabilistic circuits

Mathematics Subject Classification ID

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

Uniform proofs of ACC representations ⋮ Dual VP classes ⋮ Unnamed Item