# Which non-regular languages are in $AC^0$?

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.

• Palindromes ( $\{w w^R\}$ ) – Vor Feb 12 '13 at 17:25
• What is $AC^0$? – vonbrand Feb 12 '13 at 19:04
• @vonbrand, $AC^0$ is the class of constant depth circuits containing and/or gates of unbounded fan-in. That is, each gate in a circuit is either an "and" or an "or" gate, and allow an unbounded number of inputs coming in. – Nicholas Mancuso Feb 12 '13 at 21:20

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!

• Do you have some references to this? Especially that unary halting problem is in $AC^0$. Since $AC^0 \subseteq AC = NC \subseteq P$, I don't get this (it's late where I am, that might be my excuse). – Pål GD Feb 13 '13 at 0:19
• It's nonuniform $AC^0$ (like $P/poly$), where the circuit can arbitrarily vary with input length. – sdcvvc Feb 13 '13 at 0:34
• @PålGD, it is laid out in the Arora and Barak text. – Nicholas Mancuso Feb 13 '13 at 2:02
• Do you have a reference for a proof that multiplexing is in AC0? – Alex Grilo Feb 18 '13 at 19:45
• @Alex Grilo, unfortunately no; I think it's folklore. Just do $\bigvee_{i=0}^{2^n-1} (x=i \wedge w[i]=1)$. – sdcvvc Feb 18 '13 at 20:44