Let M be a finite monoid. A program over M is a sequence of instructions (i, x, y)

where i is a number in {1,..,n} and x and y are elements of M.

The program computes a function from {0,1}^n to M.

The yield of an instruction (i, x, y) is x if the variable x_i is false and y if x_i is true.

The yield of a program is the (ordered) product of the yields of its instructions.

The length of a program is the number of instructions in it.

A family of programs, one program P_n for each natural number n, can decide

a language A (a subset of {0,1}^*) -- for each n we have a subset X_n of M,

and a string w of length n is in A iff P_n(w) is in X_n.

If M is any non-abelian group, and A is any language, then there exists a family of programs over M

that decides A.

PROOF: Given the language A, a subset of Σ*, we can construct a family of programs, B, such that for any string w and number n where |w|=n, B_n(w)=1 iff w is in A.

That is, the yield of the program B over M will be exactly the entirety of the language A.

We separate the strings in A by length, such that each length n has its own program B_n that decides this subset of Σ^n.

For each string w of length n in this subset, Σ^n ∩ A, we produce a program that outputs the identity if w is the input, and a string c if it is not.

We construct this program on the basis that M is non-abelian. If aba^(-1)b^(-1)=c, this means that c is not equal to the identity. Using this formula, we set a as our input and b as w. Our program will output c iff w is not the input.

To construct the program itself, we use induction on n.

For n=1, we simply include an instruction that yields c if x_1=w_1, and the identity otherwise.

For n=2, we include 4 instructions: (x_=w_1, a), (x_=w_1, b), (x_=w_1, a^(-1)), (x_=w_1, b^(-1)).

For n>2, we define c' to be a^(-1)b^(-1)ab. Again, c' cannot equal the identity as M is a non-abelian group. Note that b^(-1)a^-(1)cba = c' and that bac'b^(-1)a^(-1)=c.

Using these properties, we construct programs that yield c' when n is odd and x=w (using the first statement and by adding instructions much as we did for n=2), and c when n is even and x=w (with the second statement). Note that the number of instructions approximately doubles every time n is incremented.

This process produces a family of programs whose collective yields will decide A.

-- NkanthaV - 2012-05-08

Barrington's Theorem:

If A is any language in NC^1, and M is a non-solvable group, then there exists a family of programs

over M, of polynomial length, that decides A.

-- BarrinG - 2012-04-02

PROOF: In order to prove this, we can use a lemma from the Circuits page: Any circuit in NC^1 can be simulated by a program, specifically a poly-size program over S_n or some other non-solvable group. (Note that this lemma still has not been proved on that page.)

Because A is a language in NC^1, it can decided by a family of circuits, C, consisting of n circuits, C_n.

Each of these circuits, from our lemma, can be simulated by a poly-size program, B_n.

Therefore, we can simply convert each circuit C_n to its equivalent program B_n, to produce a family of poly-size programs over M for any language A in NC^1.

-- NkanthaV - 2012-05-10

Topic revision: r6 - 2012-05-11 - NkanthaV    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