At the end of the regular 401 class we will talk about circuit complexity, the study

of the resources needed to decide a formal language with a circuit family. If X is

a subset of {0,1}*, a circuit family deciding X is a family of circuits {C_n: n >= 0}

such that circuit C_n has n boolean inputs and outputs 1 on input w of length n iff w is in X.

The size and depth of C_n are functions of n, and we define circuit complexity classes

by placing restrictions on these functions.

PSIZE = {X: exists a circuit family {C_n} deciding X with size(n) = n^{O(1)}}

NC^1 = {X: exists a circuit family for X with depth(n) = O(log n)}

AC^0 = {X: exists a circuit family for X with unbounded fan-in AND and OR gates, with size(n) = n^{O(1)} and depth(n) = O(1).}

Any first-order definable language is in AC^0.

PROOF: Given any quantified FO[≤] formula φ, a non-uniform circuit family {C_n} of poly size and constant depth can be constructed such that C(w) = 1 iff w satisfies φ, where w is a binary string. The construction is as follows: translate φ into prenex normal form, that is, change it into a formula where all of the quantifiers come first.

Next, construct an n-ary tree with depth equal to the number of quantifiers in φ. The gates at each level are AND gates if the corresponding quantifier is "∀", OR gates if it is "&exists". Each path through this tree corresponds to a different setting of the bound variables of φ, with the wires ordered exactly as the input positions.

At each leaf of the quantifier tree, we construct the straightforward translation of the boolean connectives from φ into their corresponding gates.

Finally, the predicates are translated as follows: I_1(x) is a wire to the input position corresponding to x on this branch of the quantifier tree, I_0(x) is the same, but with an intervening NOT gate.

The =(x,y) predicate is a constant TRUE gate if x and y took the same branch in the quantifier tree, FALSE if they did not. Similarly, the ≤(x,y) predicate is a constant TRUE gate if the input position to which x was bound is no greater than the one to which y was bound.

-- DstubbS - 2012-04-29

Any regular language is in NC^1.

PROOF: Let L(M) be a regular language, the language representing a DFA M.

M can be represented as a delta function as such: δ*: Σ*→(Q→Q), where Q is the set of states, Σ* is the set of all possible strings, and Q→Q is a finite monoid.

Therefore, if M is given a string w in Σ* and state x in Q, δ*(w)(x) outputs a state y in Q.

δ* can be represented as the composition of some number of δ: Σ→(Q→Q).

In other words, δ*(w) = δ(w1)°δ(w2)°δ(w3)°.....δ(wn), where each δ's monoid outputs the next state, composing a path of states to traverse for any string in Σ*.

To convert these monoids into circuits, we can create a circuit that composes together the n elements of (Q→Q).

Each individual circuit will then compose two of these elements at a time, reflecting the composition of δ*(w).

Composition is done in constant time and depth, so using this procedure, we can create a circuit family for any regular language, proving that any regular language is in NC^1.

-- NkanthaV - 2012-04-28

Any circuit in NC^1 can be simulated by a Program Over a Monoid , specifically a poly-size program over S_n or some other non-solvable group. (NEEDS PROOF)

There are also lots of other interesting examples of NC^1 circuit families, like for the majority function, multiplication of binary integers, and like that. This is a good opportunity for someone who wants to do less algrebraic stuff.

-- BarrinG - 2012-04-17

I am willing to prove the first statement. I will also construct NC^1 circuit families for the two examples listed above.

-- PkritikO - 2012-04-30

Topic revision: r10 - 2012-05-11 - NkanthaV

 Home H401 Web View Edit Account
Copyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding UMass CS EdLab? Send feedback