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 Mod_p gates that can compute the Mod_q function.
• Clique and Matching do not have polynomial-size monotone circuits even with arbitrary depth.
• *NEXP does not have constant-depth circuits with Mod_m gates for any fixed m, prime or composite. 

Links:

• The Complexity of Finite Functions by Ravi Boppana and Michael Sipser. A wonderful survey that covers definitions, results, proofs and references of the major circuit functions (except * which came after this survey).
• Nonuniform ACC Circuit Lower Bounds by Ryan Williams. This is the paper proving *.