A Note on Nonuniform versus Uniform ACC^k Circuits for NE

2010/12/02 by Hemaspaandra, Lane A.
#68Q15 #68Q17 #Computational Complexity (cs.CC) #F.1.3 #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1012.0556

Abstract

We note that for each k ∈ 0,1,2, ... the following holds: NE has (nonuniform) ACC^k circuits if and only if NE has P^NE-uniform ACC^k circuits. And we mention how to get analogous results for other circuit and complexity classes.

Related

• A Casual Tour Around a Circuit Complexity Bound
• Extensional Uniformity for Boolean Circuits
• Model-Theoretic Characterizations of Boolean and Arithmetic Circuit Classes of Small Depth
• Lower Bound for General Circuits Computing Clique Function
• Algorithms versus Circuit Lower Bounds