Introduction to Circuit Complexity

Juspreet Singh Sandhu

May 24, 2016

I want to talk about the foundations of Circuit Complexity Theory. In my

ﬁrst post I talked about Automorphisms (in Group Theory), as Quora users

particularly like to talk about it and it’s a popular topic. Now, I want to in-

troduce a topic that is hardly ever talked about on Quora. It’d be great to

see more questions on this subject here. I want to take this opportunity to get

people interested in it, and get more dialogue on it.

In this Post, I’m going to introduce the basics of Circuits from a Complex-

ity perspective, talk about how circuits are modeled as Directed Graphs, the

De-Morgan Basis (and a T h

regarding complete, minimal bases), certain

elementary Boolean Functions, and the deﬁnition of AC

(in particular AC

)

reductions and examples of some AC

reductions. I will end with a theorem

relating N C

and AC

reductions.

Let’s begin. To do so, I shall ﬁrst introduce a k-DNF, a k-CNF, and an in-

tuitive way to build a k

‘

− CN F from a k − DNF. (For those of you familiar

with these deﬁnitions, feel free to skip this part)

Def

: Given a f : {0, 1}

→ {0, 1} , ∃ an OR of a number of AND clauses

called a k − DN F (f) ,  , f

∼

k − DNF (f)

Algorithm 1 - CONVERT(f → k-DNF(f)):

- Draw Truth-Table for f.

- ∀x ∈ {0, 1}

,  , f (x) = 1 , create a clause

- if (x

= 1) , the clause should contain x

, else ¯x

- For every clause, stitch them together with OR symbols

Output : k −DNF(f) =



i=1

, where , c



j=1

σ(x

) , where , σ(x

) = x

, if , x

is in the clause , and ¯x

if that is in the clause.

Now that we know how to construct a k−DNF , let’s construct a k

‘

−CN F for f

Def

: Given a f : {0, 1}

→ {0, 1} , ∃ an AND of a number of OR clauses

called a k

‘

− CNF ,  , f

∼

‘

− CNF (f)

Algorithm 2 - CONVERT(k-DNF(f) → k

‘

-CNF(f)):

- Draw a Truth-Table for f.

- Negate the Truth-Table ((1 → 0) ∧ (0 → 1) )

- Construct the k

‘

− DNF for the Negated Truth Table. This is k

‘

DNF (

f),

and it is equivalent to

- Now, using De-Morgan’s Law : ¬(A ∧ B) = ¬A ∨ ¬B

¬(A ∨ B) = ¬A ∧ ¬B

- So, ¬ (k

‘

DNF (

f)) = f = ¬ (





i=1

(



j=1

σ(x

))) =





i=1

(



i=1

σ(x

))

Output : k

‘

− CNF (f) =





i=1

(



i=1

σ(x

))

So, it is obvious from the above that every Boolean Function can be repre-

sented as a k-DNF and a k

‘

-CNF.

Now that we know about the representation of Boolean Functions (and essen-

tially, every Boolean Function is modeling a Decision Problem) , let us deﬁne

a Circuit.

Informally, a Circuit, is a Directed Acyclic Graph with source nodes and sink

nodes. For our purposes of modeling Boolean Functions, we will look at special

kinds of Circuits (Boolean Circuits).

For modeling Boolean Functions we usually refer to a certain class of cir-

cuits called Boolean Circuits (which are leveled). A leveled circuit is one

where nodes (representing some Logical Operation over a basis) at the same

depth are aligned,  , nodes(level(s + 1)) have inputs that are the outputs of

nodes(level(s)). Fan-in refers to the in-degree of a node, and fan-out refers to

the out-degree.

It may also be known that we are interested in Boolean Circuits with just 1

sink, that is, the sink node containing the ﬁnal output {0, 1} of the Boolean

Function we are modeling as a circuit.

The De-Morgan basis is a minimal set of operations which may be combined to

model all boolean functions.

De-Morgan Basis Ω = {





, 0, 1}

Def

: Given a n-ary boolean function f : {0, 1}

→ {0, 1} , it is modeled

by a Circuit C , where, the Circuit is a *Fan-Out 1 Boolean Circuit *over the

De-Morgan Basis Ω.

The size of a circuit is the total number of Gates it has, while the depth is :

argmax(—p(i, o)—) , where i is an input node, and o is the output node.

- Input nodes (source) v

compute the target boolean function : f (x) , x ∈ B

- Non-Input nodes v

with in-degrees from a set of nodes {v

, .., v

} computes

the function g(f

(x), . . . , f

(x))

- C

Ω

(f) : Minimum size of a circuit that computes f over Ω

- L

Ω

(f) : Minimum size of a boolean formula that computes f over Ω

Now that we are aware of the Circuits we’re interested in, know the deﬁni-

tions of some of the basic terminology involved, and understand the De-Morgan

Basis, let’s introduce a few elementary boolean functions.

Elementary Boolean Functions:

i) Majority Function:

MAJ

, .., x

) =



1, if



i=1

) ≥

0, otherwise

ii) Threshold Function :

(T H

)

, .., x

) =



1, if



i=1

) ≥ k

0, otherwise

iii) Exact Function :

(EXACT

)

, .., x

) =



1, if



i=1

) = k

0, otherwise

In addition to these 3 basic functions, let me introduce a very powerful class of

functions called Symmetric Functions :

Symmetric Function : f is symmetric, if, f(x

, .., x

) = f(x

, .., x

) , for

some permutation σ : N → N , where N = {1, 2, .., n} ( σ is a bijection)

Now comes the fun part: We shall deﬁne an AC

reduction, and see two critical

examples of the same.

Def

: An AC

reduction is a mapping that takes a Boolean Function f to

the set of boolean functions span(C) , where, the mapping constructs a Circuit

C ,  , (size(C) = Poly(n)) ∧ (depth(C) = constant) ∧ (C is unbounded fan-in)

over C (P oly(n) = n

O(1)

)

If such a Circuit exists, f is said to be AC

reducible to the set C

The examples given below are results in their own right and provide insight

into the nature of symmetric boolean functions and their richness with respect

to more intuitive and easily understandable functions such as MAJ, TH and

EXACT.

An important property of these reductions is that they are transitive. This

transitivity is the basis of creating large families of functions with deﬁned com-

putational power (where computational power is measured by Circuit size and

depth).

Claim: AC

reductions are transitive

Proof: Assume ∃f

, f

,  , f

C, for some C, and we know that

Then, we see that ∃ a Circuit C

‘

, which in the worst-case, has a size(C

‘

) =

size(Circuit

→f

)*size(Circuit

→C

) ∈ set of Polynomial Functions.

Similarly, depth (C

‘

) ≤ depth(Circuit

→f

) + depth(Circuit

→C

) is constant

(Sum of two constants is a constant).

Therefore, f

Now, for the main results:

Result 1 : f

symmetric

({0, 1,





} ∪ {(EXACT

)

: 0 ≤ k ≤ n})

Proof : Let us deﬁne the ”weight” of x as w(x) =



i=1

(x

), where:

(x

) =



1, if x

= 1

0, otherwise

We begin with a small claim:

Helper Lemma: For f

symmetric

, we know that a permutation σ : N → N ,

must preserve the weights, and therefore, ∀ x

, x

∈ B

, where, w( x

) = w( x

)

implies that w(



σ(x

)) = w(



σ(x

)).

Here is an intuitive proof behind this claim :

i) Choose all Binary Vectors in B

of w(x) = k. The number of such vectors

are





. Call this set K.

ii) Now, as the permutation is a bijection, we know that every element k ∈ K

maps to precisely one element k

‘

∈ K.

iii) Create a Directed Graph G = (V, E) , with |V | =





as follows :

∀ k ∈ K, compute σ(k) , and make an edge e = (k, σ(k)).

iv) The Created Directed Graph is a *Directed Cycle*. This follows from the

bijectivity of σ . If the Graph is **not** a cycle, then (∃ k ∈ K ,  , f(k) DNE)

OR (∃ k ∈ K ,  , it has *more* than 1 pre-image). None of these conditions

are possible. Therefore, the Graph is a Directed Cycle.

v) Now, we see that, ∀ k ∈ N , we have n disjoint cycles. Each cycle has binary

vectors of weight k. Let’s call the set of these disjoint cycles S = {C

, .., C

Now that we know, this, we know that each of the vectors in a cycle in the set

map to 0 or 1 (not both).

So, basically, ∀ x ∈ B

,  , w(x) = k (for some k) , we will deﬁne a

= 1 , if

f(x) = 1, and, a

= 0, if f (x) = 0

So, we see that each of the cycles can be mapped using an (EXACT

)

func-

tion. Depending on whether that input is actually lit up in f(x) , AND it with

. Now, any arbitrary input over B

is going to be computed by either of the

cycles and will light up depending on the value of a

and the weight of the input

itself.

So, f =



i=1

∧ (EXACT

)

) , where, a

∈ {0, 1}

Now, the size of this circuit is :

n (these are the input nodes) + (



k=1

(size(EXACT

))) + 1 node for the OR

operation =⇒ size(C) ≈ O(n

Notice, that if n increases, due to leveling, the Boolean Circuit will grow

WIDER, not DEEPER. In particular, this Circuit has depth(C) = 3.

As the Circuit has size Polynomial in n and depth that is constant over C,

f <

QED

Result 2: (EXACT

)

({





, ¬, M AJ})

Proof: The proof for this rather straightforward, once we express the TH func-

tion as a MAJ function. In particular, here are the two expressions useful for

us, given our basis :

i) (T H

)

= MAJ

, . . . , x

, 0

, 1

n−k

)

ii) (T H

k+1

)

= MAJ

, .., x

, 0

k+1

, 1

n−k−1

I leave the simple proofs for these 2 statements as exercise to the reader.

If we notice, (EXACT

)

should be 1 iﬀ (T H

)

is 1 and (T H

k+1

)

is 0.

Therefore:

(EXACT

)

= (T H

)

∧¬(T H

k+1

)

=⇒ (EXACT

)

= MAJ

, . . . , x

, 0

, 1

n−k

)∧

¬MAJ

, .., x

, 0

k+1

, 1

n−k−1

As AC

circuits can be unbounded fan-in , we see that we are done.

size(C) = O(M AJ

) ≈ O(n)

depth(C) = 3.

QED

Now, for the ﬁnal result that gives us the relationship between symmetric func-

tions and MAJ functions. This result tells us basically that given a Polynomial

size Circuit of n , we can create an arbitrarily ‘fat’, but constant depth cir-

cuit that computes symmetric functions using the power of Majority functions.

This result gives a very interesting insight on the power of majority functions to

study problems that are Group Theoretic in nature, as Groups often have Auto-

morphisms (See Post 1). Therefore, we see that the complexity of the Majority

Functions required to express symmetric functions is Polynomial with respect

to an unbounded-fan in Circuit of Majority Functions with operations over the

De-Morgan Basis. Soon, once we introduce the deﬁnition of N C

reductions,

we will see the similarity of the complexity classes of the alternating NC/AC

with the Polynomial Hierarchy.

Result 3: f

symmetric

({1, ⊕, ∧, MAJ})

Proof: We will use the transitive nature of AC

reductions, and the fact that

the disjunction of Result 1 is exclusive (i.e. , only one of the cycles will return

a 1 in the function).

Now, f

symmetric

({0, 1,





} ∪ {(EXACT

)

: 0 ≤ k ≤ n}) , where,

f =



i=1

∧ (EXACT

)

) , where, a

∈ {0, 1} .

Due to the exclusive nature of Disjunction,

f =



i=1

∧ (EXACT

)

We also know from Result 2 that,

(EXACT

)

({





, ¬, M AJ})

By transitive composition,

symmetric

({





, ¬, M AJ})

Now, ¬f = 1 ⊕ f .

Therefore, f

symmetric

({





, 1, ⊕, MAJ})

Furthermore, Result 2 makes no use of ∨.

This implies that (EXACT

)

({





, 1, M AJ}).

QED

We’ve covered a lot at this point, so I’m going to just introduce the deﬁni-

tion of NC

and AC

reductions, and leave with a Theorem that the reader

should attempt to prove.

Def

(AC

) : f <

C , if, ∃ C over C ,  , (size(C) = Poly(n)) ∧

(depth(C) = O((log(n))

)) ∧ (C is unbounded fan-in).

Def

(NC

) : f <

C , if, ∃ C over C ,  , (size(C) = Poly(n)) ∧

(depth(C) = O((log(n))

)) ∧ (C is 2 fan-in).

It is easy to see that N C

⊂ AC

NC =



∞

k=1

Theorem : N C

⊂ AC

⊂ NC

k+1

(Hint) : One can transform a n-ary AND/OR junction into a Binary Tree of

AND/OR junctions with height log(n).

1 Reference

1. Clote, Kranakis (2002). Boolean Functions and Computation Models. Pg

6-20.