3
$\begingroup$

I was reading "Some properties of MOD m circuits computing simple functions" (Amano & Maruoka, 2003) where the authors prove that every Boolean function can be computed by depth $2$ by $(MOD_2-MOD_3)$ circuit. They claim what follows:

It was known that the $OR$ function of $n$ variables, i.e., $\vee_{i=1}^n x_i$ , can be computed by a depth two $(MOD_3-MOD_2)$ circuit.

I agree with the above part and I am able to show a construction for $n$-ary $OR$. Based on this fact they note that:

This implies that every disjunction of $n$ literals, i.e., $\vee_{i=1}^n l_i$ where $l_i\in \{x_i,\overline{x_i}\}$ , also can be computed by a depth two $(MOD_3-MOD_2)$ circuit.

Which I also accept. Afterward, they set up grounds for the main proof:

Let $f$ be an arbitrary Boolean function on $n$ variables. Consider a CNF formula representing $f$, where each clause contains exactly $n$ literals. Without loss of generality, we can assume that the formula has $m\equiv 1(\mod 3)$ clauses.

So far so good. But then comes the part I get lost at:

If the value of $f$ is 0, then $m-1\equiv 0(\mod 3)$ clauses of $f$ takes value $1$, and if the value of $f$ is $1$, then all of the $m\equiv 0(\mod 3)$ clauses takes value $1$. Thus the $MOD_3$ gate, whose inputs are all $(MOD_3-MOD_2)$ circuit computing each clause in the CNF formula, evaluates the func- tion $f$

Could anyone please explain to me why the sentence

If the value of $f$ is 0, then $m-1\equiv 0(\mod 3)$ clauses of $f$ takes value $1$

is true? Isn't it possible for a CNF with $m$ clauses to evaluate to $0$ and have $m-2$ clauses true? Or $m-3$ or $m-113$. What if, for example, my CNF is a big $AND$ of $n$ variables? Then this doesn't hold, any number of clauses might be 'dead'...

(Note this is not the whole proof, you have to show how to transform this bigger circuit to a smaller one).

$\endgroup$
  • $\begingroup$ The key observation is that every clause has exactly $n$ literals which is the number of variables so $f$ is represented as "the list of non-solutions". $\endgroup$ – holf Mar 18 '18 at 8:07
  • $\begingroup$ I don't follow. Could you please give me an example? For instance what happens in the case of $AND$ (we can artificially fill each one-variable clause with $n$ copies of this variable)? $\endgroup$ – Jules Mar 18 '18 at 13:52
  • 1
    $\begingroup$ (1) You are right that a cnf can evaluate to 0 with $m-2$ satisfied clauses and that you could artificially add copies of the same variable in a clause to make it of length $n$. (2) What you should read from the proof is that you have clauses having $n$ distinct literals. So there is exactly one assignment of not satisfying a given clause (ex $x \vee y \vee z$ is not satisfied by $x=y=z=0$ only. (3) Now I agree that assuming $m=1(3)$ wlog is not completely wlog. But you could still do the same reasoning with $m=c(3)$ for some constant $c$. $\endgroup$ – holf Mar 18 '18 at 15:14
  • $\begingroup$ Pardon my lack of knowledge here then but how do we know that every function can be represented as a CNF with $n$ distinct variables in each clause? I can imagine at least one for which I don't see any construction, say $AND$ that I mentioned. $\endgroup$ – Jules Mar 18 '18 at 16:04
  • 1
    $\begingroup$ Do you see how you can do it as a DNF by writing the list of all solutions? Do it for $\neg f$ $\endgroup$ – holf Mar 18 '18 at 16:40
3
$\begingroup$

The key observation is that $f$ is not represented by any CNF but by a CNF where all clauses have $n$ literals with distinct variables where $n$ is the number of variables.

It is easy to see that such a CNF exists. Indeed, let $S$ be the set of solutions of $\neg f$. Each solution $s \in S$ can be seen as a conjunction of $n$ literals. For example, $s = \{x=0, y=1, z=0\}$ may be seen as $\neg x \wedge y \wedge \neg z$. Thus $\neg f = \bigvee_{s \in S} s$ and then $f = \bigwedge_{s \in S} \neg s$ which is a CNF formula.

Now this is important since the clauses of this CNF, let's call it $F$, are in one to one correspondance with assignments of the variables: to each clause $\neg s$ of $F$, we associate $s$, the only assignment that does not satisfy the clause. For instance, the only way not to satisfy $\neg s = x \vee \neg y \vee z$ is $s=\{x=0, y=1, z=0\}$. Thus, given an assignment, at most one clause of $F$ is not satisfied.

Now there is still something to explain. The authors claim that we can assume $m \equiv 1 \mod 3$ wlog. That is not completely true since we cannot grow the number of clauses artificially and still have the previous property. However, for the sake of their argument, it is enough to add trivial clauses such a $x \vee \neg x$ that always evaluate to $1$.

$\endgroup$
  • $\begingroup$ Doesn't the argument in the last paragraph (about adding trivial clauses) violate the assumption that all clauses contain exactly n literals with n distinct variables? Maybe one can repeat clauses instead to justify the wlog. $\endgroup$ – Jan Johannsen Mar 19 '18 at 8:44
  • $\begingroup$ It does but what is important for the proof is to have: either the number of clauses evaluating to $1$ is $1 \mod 3$ ($f$ satisfied) or $0 \mod 3$ ($f$ not satisfied). You do not really need it actually, you could work with any constant or just pad your $MOD_3$ gate with $1$ constants. Repeating a clause $C$ will not work as you may thus have $m-2$ clauses not satisfied if you plug the assignment $\neg C$. $\endgroup$ – holf Mar 19 '18 at 8:51

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.