# How powerful are nondeterministic constant-depth circuits?

A nondeterministic circuit is a Boolean circuit that has nondeterministic input wires. In other words, a nondeterministic circuit $C$ computing a Boolean function $f\colon\{0,1\}^{n}\rightarrow \{0,1\}$ on input string $x\in \{0,1\}^{n}$ outputs $1$ if and only if there exists some witness string $w\in \{0,1\}^{\mbox{poly}(n)}$ such that the output of $C$ on input $(x,w)$ is $1$.

M.J. Wolf introduced nondeterministic circuits in 1987 and showed that $\mathsf{NC}$ circuits with a polynomial amount of nondeterministic gates are equivalent to $\mathsf{NP}$, and that $\mathsf{NC}$ circuits with $O(\log n)$ nondeterministic gates are equivalent to $\mathsf{NC}$ itself.

How much more power does a polynomial amount of nondeterministic add to constant-depth circuit classes, such as $\mathsf{AC}^{0}$, $\mathsf{ACC}^{0}$, and $\mathsf{TC}^{0}$? Do these classes then contain more powerful circuit classes like $\mathsf{NC}$ or $\mathsf{P/poly}$, or even $\mathsf{NP}$?

A polynomial amount of nondeterministic bits is enough to encode the computation of a nondeterministic polynomial time algorithm. The only thing we need is to check if a given string is an accepting computation which is syntactic task that can be performed by a polynomial-size $\mathsf{AC^0}$ circuit (in fact a polynomial size CNF can do this).
If you look at the $\mathsf{NP}$-compeleteness proof of CNF-SAT (or 3SAT) you see that the part that checks if a given CNF is satisfied by a given truth assignment can be computed by an $\mathsf{AC^0}$ circuit (IIRC $\mathsf{AC^0_d}$ circuits can be evaluated by an $\mathsf{AC^0_{d+1}}$ circuit).
• A related question is to lower bound $r(f)$ = min number of nondeterministic input bits required to compute $f$ by a poly-size $AC^0$ circuits, for "simple" functions. Of particular interest is to do this for the directed st-connectivity function (on graphs with $n$ vertices). About $n\log n$ bits are then enough. But direct reduction to Parity, together with know bounds, only gives by a polylog factor smaller lower bound $\frac{n}{polylog(n)}$. Have you (or anybody else) seen some related work(s)? – Stasys Mar 24 '13 at 17:53
• @Stasys, that is a nice question (btw, why not post it as a new question?). I don't know results about simple functions case or when the number of bits is $\Omega(n/polylog(n))$. My knowledge comes mainly from proof complexity where the number of nondeterministic bits is the size of certificate/proof and also there is a similarity with the number of extension variables in extended Frege proofs. – Kaveh Mar 24 '13 at 18:31
• @Stasys, Siavosh Benabbas has an unpublished result, which IIRC states that any polynomial-time nondeterministic algorithm solving CNF-SAT$_{n,m}$ where $n$ is the number of propositional variables and $m$ is the size of the formula needs more than $n^\epsilon$ nundeterminism bits unless NP is in quasipolynomial-time. – Kaveh Mar 24 '13 at 21:45
• @ Kaveh, this is interesting ("high level") result: $n$ bits are enough for a trivial algorithm, and $n^{\epsilon}$ are necessary for any NP-algorithm! On a "low level", we can even get even optimal bounds (like that for Parity). It would be interesting to understand what kind of Switching Lemma is appropriate to analyze non-deterministic $AC^0$ circuits: restricting non-deterministic variables is dangerous, may destroy too many certificates. – Stasys Mar 25 '13 at 11:49