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
- 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. Letbe 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 ofare restricted to 0 or 1, the resulting circuit still computes
, albeit on a smaller graph.
Theorem :.
Proof : We assume that there is ancircuit (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.
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.