17

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

Gustav Nordh
  • 1,047
  • 8
  • 16
  • 4
    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 Aug 29 '17 at 19:54
  • 2
    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 Aug 29 '17 at 20:34
  • 3
    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 Aug 31 '17 at 20:14
  • 1
    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 Aug 31 '17 at 21:47
  • 1
    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 Sep 01 '17 at 05:50

1 Answers1

4

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.
Hiroki Morizumi
  • 689
  • 1
  • 6
  • 11