Problem Detail: It is well-known that every boolean function $f:{0,1}^nto {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 notequiv 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.
Asked By : Gadi A
Answered By : Kristoffer Arnsfelt Hansen
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/2103 Ask a Question Download Related Notes/Documents
