Depth-2 circuits with OR and MOD gates are not universal?
-
16-10-2019 - |
سؤال
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.
المحلول
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.