[Solved]: Which non-regular languages are in $AC^0$?

Problem Detail: 

For example, I know that the non-regular language $a^nb^n$ is in $AC^0$. I would like to know more examples like this.

Asked By : Alex Grilo

Answered By : sdcvvc

Languages in $AC^0$ can be more complicated than naive intuition might suggest.

• Obviously, $AC^0$ contains $\{a^n b^n c^n\}$, which is non-context-free.
• Every unary language is in nonuniform $AC^0$; for example, the halting problem expressed in unary.
• Addition can be implemented in $AC^0$ with a carry-lookahead adder. Here the input is $2n$ bits representing two numbers, and the output contains $n+1$ wires (equivalently, each output bit can be realized in $AC^0$)

• Multiplexing: $\{w x: |w|=2^n, |x|=n, w[x] = 1\}$ is in $AC^0$.

  A multiplexer is a function on $2^n+n$ variables which outputs the value of one of $2^n$ variables, where the index is determined by the $n$ variables. (The same holds if the index is written in unary.)

• Computation of 3SAT formulas is in $AC^0$.

  The input consists of $n$ variables, followed by some clauses, each one contains three literals, where each literal is an index of the variable (unary or binary, does not matter) and a bit indicating possible negation. You can evaluate the literals with multiplexers and then add a layer of ORs and then a big AND on top.

• $AC^0$ does not contain majority, but it contains approximate majority: a function that is equal to majority if the output is $\geq \frac{1}{2}+ \varepsilon$ zeroes or ones. See "Approximate Counting with Uniform Constant-Depth Circuits" by Ajtai.

$AC^0$ is closed under logical operations, concatenation and composition, so you can combine above examples. Now you should feel some respect for $Parity \notin AC^0$ and other circuit lower bounds!

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9704

3.2K people like this

 Download Related Notes/Documents