The class \aczero\ 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 \saczero\ is the semi-unbounded version of \aczero\ i.e., AND gates have constant fan-in.

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** :*

*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

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

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

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

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

### Like this:

Like Loading...