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.

Theorem:

Proofis closed under complementation and is not.:

Prove that is not closed under complementation.Exercise :

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 :

If a CNF or a DNF computes , thenLemma :

- each term includes at least variables, and
- there are at least terms.
Hence there is no circuit of depth two for .

We will prove this lemma for CNFs. The proof for DNFs is similar. Let be a CNF circuit computing .Proof :

- 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.

**Restriction :**Let be a circuit computing . Setting an input of to 0 (resp. 1) corresponds to deleting (resp. contracting) the corresponding edge from the input graph .

If some of the inputs of areObservation :to 0 or 1, the resulting circuit still computes , albeit on arestrictedgraph.smaller

.Theorem :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] weProof :down to depth while still computing onsquashvariables. 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.many

.Corollary :

*References :***[FSS’81]**Merrick L. Furst, James B. Saxe, and Michael Sipser.**Parity, circuits, and the polynomial-time hierarchy.***In FOCS, pages 260–270, 1981.*

You could also show the n-input AND function can’t be done in SAC0 by showing any non-trivial SAC0 circuit must accept a large number of inputs.

Yes. Thats a cool idea.