Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

1 Answer

up vote 9 down vote accepted

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!

share|improve this answer
    
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
1  
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
1  
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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