#Circuit-Complexity
1 post in tag “Circuit-Complexity”.
Circuit Complexity: AC0, NC, P/poly, and the PARITY ∉ AC0 Proof
2019-09-29A 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.