Friday, September 29, 2017

Day 16

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

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