Day 16

Karp-Lipton result that if SAT has a polynomial-size circuit family then PH = Σ^p₂.

Definitions of circuit complexity classes (NCⁱ, ACⁱ). NCⁱ is the set of languages accepted by poly-size O(logⁱ n) depth with bounded fan-in. ACⁱ circuits are the same with no restriction on fan-in.

Links:

• Some connections between nonuniform and uniform complexity classes by Richard Karp and Richard Lipton. 
• Wikipedia article on Karp-Lipton with proof. 
• Wikipedia article on NC