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.

  • $\begingroup$ Palindromes ( $\{w w^R\}$ ) $\endgroup$
    – Vor
    Feb 12, 2013 at 17:25
  • $\begingroup$ What is $AC^0$? $\endgroup$
    – vonbrand
    Feb 12, 2013 at 19:04
  • $\begingroup$ @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. $\endgroup$ Feb 12, 2013 at 21:20

1 Answer 1


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!

  • $\begingroup$ 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). $\endgroup$
    – Pål GD
    Feb 13, 2013 at 0:19
  • 1
    $\begingroup$ It's nonuniform $AC^0$ (like $P/poly$), where the circuit can arbitrarily vary with input length. $\endgroup$
    – sdcvvc
    Feb 13, 2013 at 0:34
  • $\begingroup$ @PålGD, it is laid out in the Arora and Barak text. $\endgroup$ Feb 13, 2013 at 2:02
  • $\begingroup$ Do you have a reference for a proof that multiplexing is in AC0? $\endgroup$
    – Alex Grilo
    Feb 18, 2013 at 19:45
  • 1
    $\begingroup$ @Alex Grilo, unfortunately no; I think it's folklore. Just do $\bigvee_{i=0}^{2^n-1} (x=i \wedge w[i]=1)$. $\endgroup$
    – sdcvvc
    Feb 18, 2013 at 20:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.