Monday, October 2, 2017

Day 17

P-complete sets including Monotone Circuit Value: Given a circuit of just AND/OR gates with variables set to the constants TRUE and FALSE, will the circuit evaluate to TRUE?

The major results in circuit complexity:
  • Parity requires exponential-size circuits. 
  • For distinct primes p and q, there is no polynomial-size constant-depth circuit with AND, OR, NOT and Modp gates that can compute the Modq function.
  • Clique and Matching do not have polynomial-size monotone circuits even with arbitrary depth.
  • *NEXP does not have constant-depth circuits with Modm gates for any fixed m, prime or composite.