<p>If this problem has no progress, I have an answer.</p>

<p>--</p>

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

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

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

<p>[Proof Sketch]</p>

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

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

<p>The nondeterministic upper bound proof is a construction of such nondeterministic circuit.</p>

<ol>
<li>Construct a circuit computing $Parity_{\sqrt{n}}$. (The number of gates is $o(n)$.)</li>
<li>Construct a circuit selecting $\sqrt{n}$ inputs nondeterministically. (The number of gates is $2n + o(n)$.)</li>
<li>Combine the two circuits.</li>
</ol>

CC BY-SA 4.0
2018-09-09T12:45:57.317Z
Something is wrong with the bounds. Nondeterministic complexity cannot be larger than deterministic complexity.
Emil Jeřábek
CC BY-SA 4.0
2018-09-10T13:51:37.570Z
Thank you for your answer, exactly what I was looking for!
Gustav Nordh
CC BY-SA 4.0
2018-09-09T12:02:07.870Z
2018-09-09T13:13:09.973Z
2018-09-09T13:13:09.973Z
Hiroki Morizumi
<p>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.</p>

<blockquote>
  <p>Is there an explicit (and unconditional) example in the literature
  showing that non-deterministic circuits are more powerful than
  deterministic circuits?</p>
  
  <p>In particular, do you know of a function family $\{f_n\}_{n &gt; 0}$
  computable by non-deterministic circuits of size $cn$, but not
  computable by deterministic circuits of size $(c+\epsilon)n$?</p>
</blockquote>

CC BY-SA 3.0
2017-08-29T19:54:27.097Z
I don't think that such a family is known. Here is a recent paper studying non-deterministic circuits: https://arxiv.org/abs/1504.06731 I do remember that before publishing the paper Hiroki asked a similar question here
Alexander S. Kulikov
CC BY-SA 3.0
2017-08-29T20:34:09.660Z
Thanks. I assume the question you refer to is this: https://cstheory.stackexchange.com/q/25736 which is related, but asks for lower-bounds on non-deterministic circuit complexity.
Gustav Nordh
CC BY-SA 3.0
2017-08-31T20:14:45.000Z
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.
Or Meir
CC BY-SA 3.0
2017-08-31T21:47:50.303Z
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.
Gustav Nordh
CC BY-SA 3.0
2017-09-01T05:50:52.057Z
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.
Hiroki Morizumi
<cc.complexity-theory><circuit-complexity><nondeterminism>
Example demonstrating the power of non-deterministic circuits
Gustav Nordh
# Example demonstrating the power of non-deterministic circuits

(Asked by: username_0 on 2017-08-29)

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

**Tags:** cc.complexity-theory, circuit-complexity, nondeterminism
> **Comments:**
> **username_1**: I don't think that such a family is known. Here is a recent paper studying non-deterministic circuits: https://arxiv.org/abs/1504.06731 I do remember that before publishing the paper Hiroki asked a similar question here  
> **username_0**: Thanks. I assume the question you refer to is this: https://cstheory.stackexchange.com/q/25736 which is related, but asks for lower-bounds on non-deterministic circuit complexity.  
> **username_2**: 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.  
> **username_0**: 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.  
> **username_3**: 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.  

---

## 1 answers

### Answer by username_3 on 2018-09-09. Score: 4 | Accepted answer

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.

> **Comments:**
> **username_4**: Something is wrong with the bounds. Nondeterministic complexity cannot be larger than deterministic complexity.  
> **username_0**: Thank you for your answer, exactly what I was looking for!  

---

