#P-Poly

1 post in tag “P-Poly”.

• 

  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.