6
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ 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)? $\endgroup$
    – Stasys
    Mar 24, 2013 at 17:53
  • $\begingroup$ @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. $\endgroup$
    – Kaveh
    Mar 24, 2013 at 18:31
  • $\begingroup$ @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. $\endgroup$
    – Kaveh
    Mar 24, 2013 at 21:45
  • 2
    $\begingroup$ @ 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. $\endgroup$
    – Stasys
    Mar 25, 2013 at 11:49

Your Answer

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

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