Boolean circuit complexity

Boolean circuits as a model of computation, including arithmetic circuits built from gates (adders, two's complement), parallel classes AC0, NC1 and NC, and circuit lower bounds (parity and majority not in AC0, Smolensky, Razborov's monotone bound, Shannon counting, Williams).

• Boolean circuits
• Lower bounds for AC0 circuits
• Monotone circuit lower bound for clique
• Parallel complexity class NC
• Ripple-carry adder
• Kogge–Stone adder
• Shannon's circuit-size lower bound
• Two's complement subtraction and overflow

TheoremSmolensky: parity is not in AC0(mod 3)#●ready to prove

The parity language, which accepts a bitstring exactly when an odd number of its entries are true, is not in \(\mathsf{AC}^0[3]\), the class \(\mathsf{AC}^0[m]\) for \(m = 3\) of decision problems decided by polynomial-size, bounded-depth families of well-formed flat Boolean circuits in which every mod gate has modulus \(3\).

public theorem_wanted smolensky :
    parityDec ∉ AC0Mod 3

Sources

• R. Smolensky, "Algebraic methods in the theory of lower bounds for Boolean circuit complexity", Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing (STOC 1987), 77-82.

Uses 4

Statement usesThe class \(\mathsf{AC}^0(m)\) · The parity language · Complexity classes · Decision problems

TheoremWilliams: NEXP is not contained in ACC0#●ready to prove

Some decision problem lies in NEXP but not in \(\mathsf{ACC}^0\).

public theorem_wanted williams_nexp_not_in_acc0 :
    ∃ L : MetaMathlibExt.ComplexityTheory.DecisionProblem, L ∈ NEXP ∧ L ∉ ACC0

Sources

• R. Williams, "Non-uniform ACC circuit lower bounds", Journal of the ACM 61 (2014), 1-32 (CCC 2011).

Uses 4

Statement usesThe class \(\mathsf{ACC}^0\) · The complexity class NEXP · Complexity classes · Decision problems

2 ready to prove

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.