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
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 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

mersin escort adana escort izmir escort gaziantep escort