17
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 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, 2017 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, 2017 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, 2017 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, 2017 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, 2017 at 5:50

1 Answer 1

Reset to default
4
$\begingroup$

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.
Improve this answer
$\endgroup$
2
  • $\begingroup$ Something is wrong with the bounds. Nondeterministic complexity cannot be larger than deterministic complexity. $\endgroup$
    – Emil Jeřábek
    Sep 9, 2018 at 12:45
  • $\begingroup$ Thank you for your answer, exactly what I was looking for! $\endgroup$
    – Gustav Nordh
    Sep 10, 2018 at 13:51

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.