The class consists of all uniform families of circuits of constant depth and polynomial size, with unlimited-fanin AND and OR gates. NOT gates are allowed only at the inputs. The class is the semi-unbounded version of i.e., AND gates have constant fan-in. In the class both AND and OR gates have constant fan-in. The following strict hierarchy is known.
For all prime numbers , .
Todays post is is about the following theorem.
Proof : is closed under complementation and is not.
Exercise : Prove that is not closed under complementation.
Recently I came up with an alternate proof of the above theorem using the technique of random restriction of Furst, Saxe and Sipser [FSS’81]. I think my proof can be given as a cool homework problem in introductory complexity theory course. Here it goes…..
Let be a directed simple graph (i.e., does not have self-loops or multi-edges) with and . Let represent the indegree of a vertex . Motivated by cycle languages, we define the language as follows :
is represented as where each and is in encoded as binary strings. The meaning of is that there is a directed edge from to . We may assume that circuits computing will have binary inputs in a prespecified order.
Exercise : .
Lemma : If a CNF or a DNF computes , then
- each term includes at least variables, and
- there are at least terms.
Hence there is no circuit of depth two for .
Proof : We will prove this lemma for CNFs. The proof for DNFs is similar. Let be a CNF circuit computing .
- Assume that has some term that depends on less than variables. Then when all inputs to are 0, outputs 0 and hence outputs 0. Consider the graph consisting of a cycle on vertices (say ) and an isolated vertex . Note that . Let be the graph obtained by adding the edge to . Now for . If does not depend on all variables of the form then outputs 0 for some , which is a contradiction.
- Consider the graph consisting of a cycle on vertices (these are the vertices from except ) and an isolated vertex . must output zero on for . outputs 0 only when one of the terms (OR gates) outputs zero. But each OR gate outputs 0 on exactly one assignment of the input variables, Hence, must have at least terms.
Observation : If some of the inputs of are restricted to 0 or 1, the resulting circuit still computes , albeit on a smaller graph.
Theorem : .Proof : We assume that there is an circuit (say of some constant depth ) computing and derive a contradiction. Using the random restriction technique of [FSS’81] we squash down to depth while still computing on many variables. This squashing still preserves the constant fanin of AND gates. We repeat this method times to obtain an circuit of depth 2 with constant AND fanin, which contradicts the previous lemma.
Corollary : .
- [FSS’81] Merrick L. Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. In FOCS, pages 260–270, 1981.