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$
$\endgroup$
3
-
$\begingroup$ Palindromes ( $\{w w^R\}$ ) $\endgroup$– VorCommented Feb 12, 2013 at 17:25
-
$\begingroup$ What is $AC^0$? $\endgroup$– vonbrandCommented 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$– Nicholas MancusoCommented Feb 12, 2013 at 21:20
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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$– John K.Commented 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$– sdcvvcCommented Feb 13, 2013 at 0:34
-
$\begingroup$ @PålGD, it is laid out in the Arora and Barak text. $\endgroup$ Commented Feb 13, 2013 at 2:02
-
$\begingroup$ Do you have a reference for a proof that multiplexing is in AC0? $\endgroup$ Commented 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$– sdcvvcCommented Feb 18, 2013 at 20:44