On Limited Nondeterminism and ACC Circuit Lower Bounds

DOI10.1007/978-3-319-30000-9_25zbMath1443.68064MaRDI QIDQ2798730

Holger Spakowski

Publication date: 13 April 2016

Published in: Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-30000-9_25

zbMATH Keywords

EXP; circuit lower bounds; ACC

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

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

68Q06: Networks and circuits as models of computation; circuit complexity