<p>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).</p>

<p>Another way to look at this is to consider the Tseitin translation from arbitrary circuits to CNFs which has a polynomial size increase and uses only polynomially many new propositional variables. </p>

<p>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).</p>

CC BY-SA 3.0
2013-03-24T17:53:34.020Z
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](http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/thm12.12.html) 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
CC BY-SA 3.0
2013-03-24T18:31:27.067Z
@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
CC BY-SA 3.0
2013-03-24T21:45:46.483Z
@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
CC BY-SA 3.0
2013-03-25T11:49:38.763Z
@ 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
CC BY-SA 3.0
2013-03-24T08:21:23.077Z
2013-05-03T16:02:15.667Z
2013-05-03T16:02:15.667Z
Kaveh
<p>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$.</p>

<p>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.</p>

<p>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}$?</p>

<cc.complexity-theory><reference-request><complexity-classes><circuit-complexity><nondeterminism>
How powerful are nondeterministic constant-depth circuits?
echuly
# How powerful are nondeterministic constant-depth circuits?

(Asked by: username_0 on 2013-03-24)

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}$?

**Tags:** cc.complexity-theory, reference-request, complexity-classes, circuit-complexity, nondeterminism


---

## 1 answers

### Answer by username_1 on 2013-03-24. Score: 7 | Accepted answer

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).

Another way to look at this is to consider the Tseitin translation from arbitrary circuits to CNFs which has a polynomial size increase and uses only polynomially many new propositional variables.

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).

> **Comments:**
> **username_2**: 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](http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/thm12.12.html) bounds, only gives  by a polylog factor smaller lower bound $\frac{n}{polylog(n)}$.  Have you (or anybody else) seen some related work(s)?  
> **username_1**: @username_2, 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.  
> **username_1**: @username_2, 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.  
> **username_2**: @ username_1, 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.  

---

