Week Two: Boolean Circuits

Question 1

Define a boolean circuit

Answer 1

An n-input Boolean circuit C is a directed acyclic graph with:
▶ n sources x1, . . . , xn (vertices with no incoming edges);
▶ one sink s (vertex with no outgoing edges);
▶ a labelling from nonsource vertices to {¬, ∨, ∧} (called gates);
▶ vertices labelled ¬ have fan-in (i.e. number of incoming edges) 1;
▶ vertices labelled ∨ or ∧ have fan-in 2.
The size of C , written |C |, is its number of vertices.

Question 2

How do we define the value of a boolean circuit node?

Answer 2

By induction on the structure of C :
▶ labelled ¬ with incoming edge from a node u, then b(v ) := 1 − b(u).
▶ labelled ∨ with incoming edges from nodes u0 and u1, then b(v ) := max(b(u0), b(u1)).
▶ labelled ∧ with incoming edges from nodes u0 and u1, then b(v ) := min(b(u0), b(u1)).

From here, we can define the output b(C ) of C as just b(s).

Question 3

What is formula unfolding?

Answer 3

If L ⊆ {0, 1}^n is computed by a circuit C of depth d, then it is computed by a formula of size < 2^d.

Question 4

When can we say a language is computed by a circuit family?

Answer 4

We say that a language L ⊆ {0, 1}∗ is computed by a circuit family
{Cn}1 to ∞ if, for each n ∈ N, Cn is an n-input circuit computing L ∩ {0, 1}^n.

Question 5

Explain SIZE and DEPTH ?

Answer 5

SIZE(f (n)) is the set of languages L ⊆ {0, 1}∗ computed by circuits
of size ≤ f (n).
DEPTH(f (n)) is the set of languages L ⊆ {0, 1}∗ computed by
circuits of depth ≤ f (n).

Question 6

What boolean circuit functions were provided in lectures?

Answer 6

EXACT^n k (x1, …, xn) = 1 when k xs are 1.
Same for ATMOST.

LEQ^n (xs, ys) = 1 when number coded by xs <= number coded by ys.
Same for NEQ.

MAJ^n(xs) = majority of 1s.

Question 7

What theorem relates to unary languages?

Answer 7

Let L ⊆ {0, 1}* be a unary language, i.e. L ⊆ {1n : n ∈ N}. Then
L ∈ P/poly .

Question 8

What is the circuit SAT problem?

Answer 8

The circuit satisfiability problem is the set of circuits C (x1, . . . , xn) for which there exists an input b ∈ {0, 1}^n s.t. C (b) = 1.

Theorem: Circuit satisfiability is NP-complete.

Question 9

What is L-Uniform?

Answer 9

A circuit family {Cn}1 to ∞ is L-uniform if the data SIZE(n), TYPE(n, i)
and EDGE(n, i, j) are computable in O(log n) space.

SIZE(n) = on input n ∈ N returns the size of the circuit Cn.
TYPE(n, i) = on inputs n ∈ N and i < SIZE(n) returns the label of the ith vertex of Cn.
EDGE(n, i, j) = on inputs n ∈ N and i, j < SIZE(n), is true when there is an edge from the ith vertex of Cn to the jth vertex of Cn.

L ⊆ {0, 1}* has L-uniform polynomial-size circuits ⇐⇒ L ∈ P.