The Complexity of Problems Defined by Boolean Circuits
Steffen Reith, Klaus W. Wagner · 2005
We study the complexity of circuit-based combinatorial problems (e.g., the circuit value problem and the satisfiability problem) defined by boolean circuits with gates from an arbitrary finite base B of boolean functions. Special cases have been investigated in the literature. We give a complete characterization of their complexity depending on the base B. For example, for the satisfiability problem for boolean circuits with gates from B we present a complete collection of (decidable) criteria which tell us for which B this problem is in L, is complete for NL, is complete for L, is complete for P, or is complete for NP. Our proofs make substantial use of the characterization of all closed classes of boolean functions given by E.L. POST already in the twenties.