HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Depth-2 circuits with OR and MOD gates are not universal?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
depthwithareuniversalgatesmodcircuitsandnot

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#2103, answer score: 10

Revisions (0)

No revisions yet.