Circuit-Complexity

• Circuit Complexity: AC0, NC, P/poly, and the PARITY ∉ AC0 Proof · 2019-09-29

  A rigorous journey through circuit complexity classes—AC0, NC, P/poly—and the landmark result that PARITY cannot be computed by constant-depth polynomial-size circuits.