9
$\begingroup$

It is well-known that every boolean function $f:\{0,1\}^n\to \{0,1\}$ can be realized using a boolean circuit of depth 2 (over the variables, their negation and constant values) containing AND gates in the first level and one single OR gate in the upper level; this is simply the DNF representation of $f$.

Another type of gate which is of great interest in circuit complexity is the $MOD_m$ gate. The usual definition is the following:

$$\mathrm{MOD}_m(x_1,\dots,x_k)=\cases{ 1 & if \(\sum x_i \equiv 0 \mod m\) \\ 0 & if \(\sum x_i \not\equiv 0 \mod m\) \\ }$$

These gates sometimes have surprising power; for example, any boolean function can be represented by a depth-2 circuit having only $\mathrm{MOD}_6$ gates (this is folklore but I can elaborate is someone is interested).

However, another folklore is that circuits with a single OR gate at the top and $\mathrm{MOD}_m$ gates in the bottom layer (with $m$ being fixed once and for all, and in particular being the same for all the gates) is not universal, i.e. for any value of $m$, there are boolean functions that cannot be computed by $\mathrm{OR} \circ \mathrm{MOD}_m$ circuit.

I'm looking for a proof for this claim, or at least some direction.

$\endgroup$
  • 1
    $\begingroup$ In the first paragraph, either you need NOT gates or you have to say “every monotone Boolean function.” $\endgroup$ – Tsuyoshi Ito May 27 '12 at 12:44
  • $\begingroup$ You are correct; the usual assumption is that you have as inputs the variables, their negation and also arbitrary values (important for modgates). I'll write this explicitly. $\endgroup$ – Gadi A May 27 '12 at 12:46
  • 1
    $\begingroup$ I guess that $n$, the number of input variables, is different from $n$, the modulus? $\endgroup$ – Kristoffer Arnsfelt Hansen May 27 '12 at 15:45
  • $\begingroup$ Yes, sorry about that. $\endgroup$ – Gadi A May 27 '12 at 16:10
  • $\begingroup$ I am interested on this. Do you know some reference for the first folkloric fact? I wonder, if in the latter class of circuits you only allow one OR, how many do you allow in the former? $\endgroup$ – Juan Bermejo Vega May 28 '12 at 12:01
8
$\begingroup$

The Boolean AND function can not be computed. Suppose actually that the AND function is computed by an $\text{OR} \circ \text{MOD}$ circuit. Then it follows that one of the MOD subcircuits must compute then AND function already, which is impossible.

$\endgroup$
  • $\begingroup$ No, he's correct. The implicit assumption here is that n is constant and we should be able to handle an arbitrarily large number of inputs with mod_n gates. $\endgroup$ – Gadi A May 27 '12 at 16:20
  • $\begingroup$ @GadiA Ah, ok. This wasn't clear in your question, at least to people who aren't familiar with the field. I've made a minor edit that should clarify this. $\endgroup$ – Gilles May 27 '12 at 16:28
  • $\begingroup$ Yes, my question was very badly phrased, sorry. $\endgroup$ – Gadi A May 27 '12 at 16:29
  • $\begingroup$ @Gilles Can you explain me what fan-in here we consider ? The problem for me is that I can't see why subcircuit of MOD can't compute AND ? How many inputs has this MOD and this AND ? $\endgroup$ – user54001 Apr 27 '17 at 17:31

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.