A non-deterministic Boolean circuit has, in addition to the ordinary inputs $x = (x_1,\dots,x_n)$, a set of "non-deterministic" inputs $y=(y_1,\dots,y_m)$. A non-deterministic circuit $C$ accepts input $x$ if there exists $y$ such that the circuit output $1$ on $(x,y)$. Analogous to $P/poly$ (the class of languages decidable by polynomial size circuits), $NP/poly$ can be defined as the class of languages decidable by polynomial size non-deterministic circuits. It is widely believed that non-deterministic circuits are more powerful than deterministic circuits, in particular $NP \subset P/poly$ imply that the polynomial hierarchy collapses.

Is there an explicit (and unconditional) example in the literature showing that non-deterministic circuits are more powerful than deterministic circuits?

In particular, do you know of a function family $\{f_n\}_{n > 0}$ computable by non-deterministic circuits of size $cn$, but not computable by deterministic circuits of size $(c+\epsilon)n$?

  • 4
    $\begingroup$ I don't think that such a family is known. Here is a recent paper studying non-deterministic circuits: arxiv.org/abs/1504.06731 I do remember that before publishing the paper Hiroki asked a similar question here $\endgroup$ – Alexander S. Kulikov Aug 29 '17 at 19:54
  • 2
    $\begingroup$ Thanks. I assume the question you refer to is this: cstheory.stackexchange.com/q/25736 which is related, but asks for lower-bounds on non-deterministic circuit complexity. $\endgroup$ – Gustav Nordh Aug 29 '17 at 20:34
  • 3
    $\begingroup$ One important property of non-deterministic circuits is that they can always be transformed into equivalent depth-2 circuits by adding more non-deterministic inputs, using the same ideas as in the reduction from CircuitSAT to SAT. In particular, this means that non-deterministic circuits of depth 2 can compute the parity of n bits in polynomial size, while deterministic circuits of depth 2 computing parity must be of size 2^n-1. $\endgroup$ – Or Meir Aug 31 '17 at 20:14
  • 1
    $\begingroup$ Good point! Especially in relation to Hiroki's result mentioned above that the non-deterministic circuit complexity of parity is 3(n-1), which is equal to the deterministic circuit complexity of parity. $\endgroup$ – Gustav Nordh Aug 31 '17 at 21:47
  • 1
    $\begingroup$ The case of DeMorgan formulas is similar to depth-2 circuits mentioned above. Non-deterministic DeMorgan formulas can compute the parity of n bits in linear size, using the similar ideas as depth-2 circuits, while deterministic DeMorgan formulas need quadratic size by Khrapchenko's theorem. $\endgroup$ – Hiroki Morizumi Sep 1 '17 at 5:50

If this problem has no progress, I have an answer.


I also have considered this problem since my COCOON'15 paper (before your question).

Now, I have a proof strategy, and it immediately gives the following theorem: There is a Boolean function $f$ such that the nondeterministic $U_2$-circuit complexity of $f$ is at most $2n + o(n)$ and the deterministic $U_2$-circuit complexity of $f$ is $3n - o(n)$.

I apologize that I haven't written the paper. The proof sketch below might be enough to explain my proof strategy. I aim to write the paper with more results by the STACS deadline (Oct. 1).

[Proof Sketch]

Let $f = \lor_{i=0}^{\sqrt{n}-1}{Parity_{\sqrt{n}}(x_{\sqrt{n} \cdot i + 1}, \ldots, x_{\sqrt{n} \cdot i + \sqrt{n}}})$.

The deterministic lower bound proof is based on a standard gate elimination method with a little modification.

The nondeterministic upper bound proof is a construction of such nondeterministic circuit.

  1. Construct a circuit computing $Parity_{\sqrt{n}}$. (The number of gates is $o(n)$.)
  2. Construct a circuit selecting $\sqrt{n}$ inputs nondeterministically. (The number of gates is $2n + o(n)$.)
  3. Combine the two circuits.
  • $\begingroup$ Something is wrong with the bounds. Nondeterministic complexity cannot be larger than deterministic complexity. $\endgroup$ – Emil Jeřábek Sep 9 '18 at 12:45
  • $\begingroup$ Thank you for your answer, exactly what I was looking for! $\endgroup$ – Gustav Nordh Sep 10 '18 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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